제출 #991105

#제출 시각아이디문제언어결과실행 시간메모리
991105borisAngelovTraffic (IOI10_traffic)C++17
50 / 100
1085 ms262144 KiB
#include "traffic.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1000005; const long long inf = (1LL << 60); int n; int a[maxn]; vector<int> g[maxn]; struct SegmentTree { long long tree[4 * maxn]; long long lazy[4 * maxn]; void pushLazy(int node, int l, int r) { tree[node] += lazy[node]; if (l != r) { lazy[2 * node] += lazy[node]; lazy[2 * node + 1] += lazy[node]; } lazy[node] = 0; } void update(int node, int l, int r, int ql, int qr, long long delta) { pushLazy(node, l, r); if (l > qr || r < ql) { return; } if (ql <= l && r <= qr) { lazy[node] += delta; pushLazy(node, l, r); return; } int mid = (l + r) / 2; update(2 * node, l, mid, ql, qr, delta); update(2 * node + 1, mid + 1, r, ql, qr, delta); tree[node] = max(tree[2 * node], tree[2 * node + 1]); } long long query(int node, int l, int r, int ql, int qr) { pushLazy(node, l, r); if (l > qr || r < ql) { return -inf; } if (ql <= l && r <= qr) { return tree[node]; } int mid = (l + r) / 2; return max(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr)); } }; SegmentTree tree; long long subtreeSum[maxn]; long long ans[maxn]; void dfsInit(int node, int par) { subtreeSum[node] = a[node]; for (int i = 0; i < g[node].size(); ++i) { if (g[node][i] != par) { dfsInit(g[node][i], node); subtreeSum[node] += subtreeSum[g[node][i]]; } } tree.update(1, 1, n, node, node, subtreeSum[node]); } void dfsSolve(int node, int par) { if (1 < node && node < n) { ans[node] = max(tree.query(1, 1, n, 1, node - 1), tree.query(1, 1, n, node + 1, n)); } else if (node == 1) { ans[node] = tree.query(1, 1, n, 2, n); } else { ans[node] = tree.query(1, 1, n, 1, n - 1); } for (int i = 0; i < g[node].size(); ++i) { int to = g[node][i]; if (to != par) { subtreeSum[node] -= subtreeSum[to]; tree.update(1, 1, n, node, node, -subtreeSum[to]); subtreeSum[to] += subtreeSum[node]; tree.update(1, 1, n, to, to, +subtreeSum[node]); dfsSolve(to, node); tree.update(1, 1, n, to, to, -subtreeSum[node]); subtreeSum[to] -= subtreeSum[node]; tree.update(1, 1, n, node, node, +subtreeSum[to]); subtreeSum[node] += subtreeSum[to]; } } } int LocateCentre(int N, int pp[], int S[], int D[]) { n = N; for (int i = 1; i <= n; ++i) { a[i] = pp[i - 1]; } for (int i = 1; i <= n - 1; ++i) { int x = S[i - 1]; int y = D[i - 1]; ++x; ++y; g[x].push_back(y); g[y].push_back(x); } dfsInit(1, -1); dfsSolve(1, -1); long long big = inf; int node = -1; for (int i = 1; i <= n; ++i) { //cout << i << " :: " << ans[i] << endl; if (big > ans[i]) { big = ans[i]; node = i; } } //cout << big << endl; return node - 1; }

컴파일 시 표준 에러 (stderr) 메시지

traffic.cpp: In function 'void dfsInit(int, int)':
traffic.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < g[node].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~
traffic.cpp: In function 'void dfsSolve(int, int)':
traffic.cpp:112:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |     for (int i = 0; i < g[node].size(); ++i)
      |                     ~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...