Submission #2697627
Source Code Expand
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
vector <pair <int, int> > g[N];
vector <int> all, temp[N], pref_all, pref_temp[N];
int dp[N], ans[N], dist[N];
bool visited[N];
void dfs (int u, int p) {
dp[u] = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
if (v != p && !visited[v]) {
dfs(v, u);
dp[u] += dp[v];
}
}
}
int find_centroid (int u, int p, int sz) {
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
if (v != p && !visited[v] && dp[v] > sz/2) return find_centroid(v, u, sz);
}
return u;
}
void redfs (int u, int p, int val, int branch) {
all.push_back(val);
temp[branch].push_back(val);
dist[u] = val;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
if (v == p || visited[v]) continue;
redfs(v, u, min(val,g[u][i].second), branch);
}
}
void cal (int u, int p, int branch) {
int pos_all = upper_bound(all.begin(), all.end(), dist[u]) - all.begin();
int pos_temp = upper_bound(temp[branch].begin(), temp[branch].end(), dist[u]) - temp[branch].begin();
ans[u] = ans[u] + pref_all[pos_all - 1] - pref_temp[branch][pos_temp - 1];
pos_all = (int)all.size() - pos_all;
pos_temp = (int)temp[branch].size() - pos_temp;
ans[u] = ans[u] + (pos_all - pos_temp + 1) * dist[u];
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first;
if (visited[v] || v == p) continue;
cal(v, u, branch);
}
}
void centroid (int root) {
dfs(root, root);
if(dp[root] == 1) return;
int cen = find_centroid(root, root, dp[root]);
visited[cen] = true;
all.clear();
pref_all.clear();
for (int i = 0; i < g[cen].size(); i++) {
int v = g[cen][i].first;
if (visited[v]) continue;
temp[v].clear();
pref_temp[v].clear();
redfs(v, cen, g[cen][i].second, v);
}
sort(all.begin(), all.end());
pref_all.push_back(all[0]);
for (int i = 1; i < all.size(); i++) pref_all.push_back(all[i] + pref_all[pref_all.size() - 1]);
for (int i = 0; i < g[cen].size(); i++) {
int v = g[cen][i].first;
if (visited[v]) continue;
sort(temp[v].begin(), temp[v].end());
for (int j = 0; j < temp[v].size(); j++) {
if (j == 0) pref_temp[v].push_back(temp[v][0]);
else pref_temp[v].push_back(temp[v][j] + pref_temp[v][pref_temp[v].size() - 1]);
}
cal(v, cen, v);
}
ans[cen] += pref_all[pref_all.size() - 1];
for (int i = 0; i < g[cen].size(); i++) {
int v = g[cen][i].first;
if (!visited[v]) centroid(v);
}
}
signed main(){
int n;
scanf("%lld", &n);
for (int i = 1; i <= n - 1; i++) {
int u, v, w;
scanf("%lld %lld %lld", &u, &v, &w);
g[u].push_back(make_pair(v, w));
g[v].push_back(make_pair(u, w));
}
memset(visited, 0, sizeof(visited));
memset(ans, 0, sizeof(ans));
centroid(1);
for (int i = 1; i <= n; i++) printf("%lld\n", ans[i]);
//cout << "dist " << dist[2] << "\n";
//for (int i = 0; i < all.size(); i++) cout << all[i] << " ";
//for (int i = 0; i < temp[2].size(); i++) cout << temp[2][i] << " ";
//cout << dist[1] << " " << dist[2] << " " << dist[3];
return 0;
}
/*
4
1 2 10
2 3 20
1 4 10
*/
Submission Info
Submission Time |
|
Task |
E - Black Cats Deployment |
User |
FutymyClone |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
3564 Byte |
Status |
AC |
Exec Time |
469 ms |
Memory |
53488 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:106:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &n);
^
./Main.cpp:109:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld %lld", &u, &v, &w);
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
200 / 200 |
400 / 400 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt |
Subtask2 |
00_example_02.txt, s1_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt |
All |
00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt, s3_19.txt, s3_20.txt, s3_21.txt, s3_22.txt, s3_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s3_27.txt, s3_28.txt, s3_29.txt |
Case Name |
Status |
Exec Time |
Memory |
00_example_01.txt |
AC |
4 ms |
8576 KB |
00_example_02.txt |
AC |
4 ms |
8576 KB |
00_example_03.txt |
AC |
4 ms |
8576 KB |
s1_01.txt |
AC |
5 ms |
8704 KB |
s1_02.txt |
AC |
5 ms |
8704 KB |
s1_03.txt |
AC |
5 ms |
8704 KB |
s1_04.txt |
AC |
5 ms |
8832 KB |
s1_05.txt |
AC |
6 ms |
8832 KB |
s1_06.txt |
AC |
6 ms |
8832 KB |
s1_07.txt |
AC |
4 ms |
8576 KB |
s2_08.txt |
AC |
173 ms |
29232 KB |
s2_09.txt |
AC |
102 ms |
21160 KB |
s2_10.txt |
AC |
42 ms |
14476 KB |
s2_11.txt |
AC |
200 ms |
32516 KB |
s2_12.txt |
AC |
298 ms |
38128 KB |
s2_13.txt |
AC |
328 ms |
52976 KB |
s2_14.txt |
AC |
333 ms |
52976 KB |
s3_15.txt |
AC |
222 ms |
29872 KB |
s3_16.txt |
AC |
121 ms |
21544 KB |
s3_17.txt |
AC |
50 ms |
14604 KB |
s3_18.txt |
AC |
94 ms |
19324 KB |
s3_19.txt |
AC |
244 ms |
33284 KB |
s3_20.txt |
AC |
341 ms |
38768 KB |
s3_21.txt |
AC |
250 ms |
33172 KB |
s3_22.txt |
AC |
244 ms |
33092 KB |
s3_23.txt |
AC |
345 ms |
53488 KB |
s3_24.txt |
AC |
308 ms |
39156 KB |
s3_25.txt |
AC |
469 ms |
40176 KB |
s3_26.txt |
AC |
318 ms |
40176 KB |
s3_27.txt |
AC |
464 ms |
40432 KB |
s3_28.txt |
AC |
309 ms |
40048 KB |
s3_29.txt |
AC |
457 ms |
40688 KB |