# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
102502 | 2019-03-25T12:09:07 Z | alexpetrescu | Designated Cities (JOI19_designated_cities) | C++14 | 2000 ms | 30096 KB |
#include <cstdio> #include <vector> #include <algorithm> #include <cstdlib> //FILE *fin = fopen("a.in", "r"), *fout = fopen("a.out", "w"); #define fin stdin #define fout stdout #define ll long long #define MAXN 200009 struct myc { int x, y, z; }; std::vector < int > candidat[MAXN]; std::vector < myc > g[MAXN]; ll ans[MAXN], sumaTuturor; int e[MAXN], desteptu[MAXN], istetu[MAXN]; bool viz[MAXN], luat[MAXN], seen[MAXN]; ll sum[MAXN], calc[MAXN], h[MAXN], cost[MAXN]; int t[MAXN], ind[MAXN]; int A, B, C; void dfs1(int x) { viz[x] = 1; for (auto &y : g[x]) { if (viz[y.x] == 0) { dfs1(y.x); sum[x] += sum[y.x] + y.z; } } } void dfs2(int x, ll dinSpate) { viz[x] = 1; calc[x] = sum[x] + dinSpate; ans[1] = std::min(ans[1], sumaTuturor - calc[x]); desteptu[x] = x; for (auto &y : g[x]) { if (viz[y.x] == 0) { h[y.x] = h[x] + y.y; dfs2(y.x, dinSpate + sum[x] - sum[y.x] - y.z + y.y); if (h[desteptu[y.x]] > h[desteptu[x]]) { istetu[x] = desteptu[x]; desteptu[x] = desteptu[y.x]; } else if (h[desteptu[y.x]] > h[istetu[x]]) istetu[x] = desteptu[y.x]; } } if (h[desteptu[x]] + h[istetu[x]] - h[x] + calc[x] > h[A] + h[B] - h[C] + calc[C]) A = desteptu[x], B = istetu[x], C = x; } void dfs3(int x) { viz[x] = 1; bool frunza = 1; desteptu[x] = x; for (auto &y : g[x]) { if (viz[y.x] == 0) { frunza = 0; h[y.x] = h[x] + y.y; t[y.x] = x; dfs3(y.x); if (h[desteptu[y.x]] > h[desteptu[x]]) desteptu[x] = desteptu[y.x]; luat[x] |= luat[y.x]; if (luat[y.x] == 0) ans[2] += y.y; } } if(frunza) e[++e[0]] = x; } bool cmp(const int &a, const int &b) { return h[a] > h[b]; } void dfs4(int x) { viz[x] = 1; for (auto &y : g[x]) { if (viz[y.x] == 0) { if (luat[y.x] == 0 && seen[desteptu[y.x]] == 0) { seen[desteptu[y.x]] = 1; cost[desteptu[y.x]] = h[desteptu[y.x]] - h[x]; candidat[x].push_back(desteptu[y.x]); } dfs4(y.x); } } std::sort(candidat[x].begin(), candidat[x].end(), cmp); } inline void solve(int n) { int rad = 0; for (int i = 1; i <= n; i++) if ((int)g[i].size() != 1) rad = i; ans[1] = sumaTuturor; dfs1(rad); for (int i = 1; i <= n; i++) viz[i] = 0; h[0] = cost[0] = -1000000000000000000LL; dfs2(rad, 0); for (int i = 1; i <= n; i++) viz[i] = 0; luat[A] = luat[B] = 1; h[C] = 0; dfs3(C); for (int i = 1; i <= n; i++) viz[i] = 0; dfs4(C); for (int i = 3; i <= e[0]; i++) { int best = 0; for (int j = 1; j <= n; j++) { if (luat[j]) { while (ind[j] < (int)candidat[j].size() && luat[candidat[j][ind[j]]]) ind[j]++; if (ind[j] < (int)candidat[j].size() && cost[candidat[j][ind[j]]] > cost[best]) best = candidat[j][ind[j]]; } } if (best == 0) exit(1); ans[i] = ans[i - 1] - cost[best]; while (luat[best] == 0) { luat[best] = 1; best = t[best]; } } } int main() { int n; fscanf(fin, "%d", &n); for (int i = 1; i < n; i++) { int x, y, z, t; fscanf(fin, "%d%d%d%d", &x, &y, &z, &t); g[x].push_back({y, z, t}); g[y].push_back({x, t, z}); sumaTuturor += z + t; ans[1] = std::min(z, t); } if (n > 2) solve(n); int q; fscanf(fin, "%d", &q); for (; q; q--) { int x; fscanf(fin, "%d", &x); fprintf(fout, "%lld\n", ans[x]); } fclose(fin); fclose(fout); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 10 ms | 9856 KB | Output is correct |
4 | Correct | 12 ms | 9728 KB | Output is correct |
5 | Correct | 11 ms | 9864 KB | Output is correct |
6 | Correct | 10 ms | 9856 KB | Output is correct |
7 | Incorrect | 10 ms | 9856 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9728 KB | Output is correct |
2 | Execution timed out | 2048 ms | 30024 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 13 ms | 9728 KB | Output is correct |
2 | Execution timed out | 2071 ms | 30096 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 10 ms | 9856 KB | Output is correct |
4 | Correct | 12 ms | 9728 KB | Output is correct |
5 | Correct | 11 ms | 9864 KB | Output is correct |
6 | Correct | 10 ms | 9856 KB | Output is correct |
7 | Incorrect | 10 ms | 9856 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 11 ms | 9728 KB | Output is correct |
2 | Execution timed out | 2048 ms | 30024 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 9728 KB | Output is correct |
2 | Correct | 10 ms | 9728 KB | Output is correct |
3 | Correct | 10 ms | 9856 KB | Output is correct |
4 | Correct | 12 ms | 9728 KB | Output is correct |
5 | Correct | 11 ms | 9864 KB | Output is correct |
6 | Correct | 10 ms | 9856 KB | Output is correct |
7 | Incorrect | 10 ms | 9856 KB | Output isn't correct |
8 | Halted | 0 ms | 0 KB | - |