# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
25471 | 2017-06-22T09:51:51 Z | dotorya | Election Campaign (JOI15_election_campaign) | C++14 | 569 ms | 64144 KB |
#include <stdio.h> #include <algorithm> #include <assert.h> #include <bitset> #include <cmath> #include <complex> #include <deque> #include <functional> #include <iostream> #include <limits.h> #include <map> #include <math.h> #include <queue> #include <set> #include <stdlib.h> #include <string.h> #include <string> #include <time.h> #include <unordered_map> #include <unordered_set> #include <vector> #pragma warning(disable:4996) #pragma comment(linker, "/STACK:336777216") using namespace std; #define mp make_pair #define Fi first #define Se second #define pb(x) push_back(x) #define szz(x) ((int)(x).size()) #define rep(i, n) for(int i=0;i<n;i++) #define all(x) (x).begin(), (x).end() #define ldb ldouble typedef tuple<int, int, int> t3; typedef long long ll; typedef unsigned long long ull; typedef double db; typedef long double ldb; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <ll, int> pli; typedef pair <db, db> pdd; int IT_MAX = 1 << 15; const ll MOD = 1000000007; const int INF = 0x3f3f3f3f; const ll LL_INF = 0x3f3f3f3f3f3f3f3f; const db PI = acos(-1); const db ERR = 1e-10; vector <int> conn[100050]; vector <int> son[100050]; int par[100050][20]; int sz[100050]; int dep[100050]; bool dchk[100050]; void DFS1(int n) { dchk[n] = true; sz[n] = 1; for (auto it : conn[n]) { if (dchk[it]) continue; dep[it] = dep[n] + 1; par[it][0] = n; for (int i = 1; i < 20; i++) par[it][i] = par[par[it][i - 1]][i - 1]; DFS1(it); son[n].push_back(it); sz[n] += sz[it]; } } int upnode(int n, int c) { for (int i = 18; i >= 0; i--) if (c & (1 << i)) n = par[n][i]; return n; } int lca(int a, int b) { if (dep[a] > dep[b]) swap(a, b); b = upnode(b, dep[b] - dep[a]); if (a == b) return a; for (int i = 19; i >= 0; i--) { if (par[a][i] != par[b][i]) { a = par[a][i]; b = par[b][i]; } } return par[a][0]; } vector <int> Vq[100050]; int Qu[100050][3]; map <int, ll> Mx[100050]; ll off[100050]; int pos[100050]; int pc = 0; vector <ll> Vu; set <pll> Sx; void DFS2(int n) { if (son[n].empty()) { pos[n] = ++pc; Mx[pc][n] = Mx[pc][-1] = 0; return; } for (auto it : son[n]) DFS2(it); sort(all(son[n]), [](int a, int b) { return sz[a] > sz[b]; }); ll sum = 0; for (auto it : son[n]) { Vu.push_back(Mx[pos[it]][-1] + off[pos[it]]); sum += Vu.back(); } ll toff = sum - (Mx[pos[son[n][0]]][-1] + off[pos[son[n][0]]]); ll u = sum; for (auto it : Vq[n]) { int n1 = Qu[it][0], n2 = Qu[it][1]; if (n2 == n) swap(n1, n2); ll v = sum; if (n1 != n) { int p1 = upnode(n1, dep[n1] - dep[n] - 1); v += Mx[pos[p1]][n1] - Mx[pos[p1]][-1]; } int p2 = upnode(n2, dep[n2] - dep[n] - 1); v += Mx[pos[p2]][n2] - Mx[pos[p2]][-1]; v += Qu[it][2]; u = max(u, v); } pos[n] = pos[son[n][0]]; int np = pos[n]; off[np] += toff; Mx[np][n] = sum - off[np], Mx[np][-1] = u - off[np]; for (int i = 1; i < son[n].size(); i++) { int n2 = son[n][i]; ll v = sum - Mx[pos[n2]][-1] + off[pos[n2]]; for (auto it : Mx[pos[n2]]) { if (it.first == -1) continue; Mx[np][it.first] = v + it.second - off[np]; } } } int main() { srand(time(0)); int N, Q, i, t1, t2; scanf("%d", &N); for (i = 1; i < N; i++) { scanf("%d %d", &t1, &t2); conn[t1].push_back(t2); conn[t2].push_back(t1); } int x = rand() % N + 1; for (i = 0; i < 20; i++) par[x][i] = x; DFS1(x); scanf("%d", &Q); for (i = 1; i <= Q; i++) { scanf("%d %d %d", &Qu[i][0], &Qu[i][1], &Qu[i][2]); Vq[lca(Qu[i][0], Qu[i][1])].push_back(i); } DFS2(x); return !printf("%lld\n", Mx[pos[x]][-1] + off[pos[x]]); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24796 KB | Output is correct |
2 | Correct | 3 ms | 24796 KB | Output is correct |
3 | Correct | 0 ms | 24796 KB | Output is correct |
4 | Correct | 3 ms | 25060 KB | Output is correct |
5 | Correct | 303 ms | 63972 KB | Output is correct |
6 | Correct | 139 ms | 49484 KB | Output is correct |
7 | Correct | 296 ms | 50184 KB | Output is correct |
8 | Correct | 213 ms | 52140 KB | Output is correct |
9 | Correct | 283 ms | 50248 KB | Output is correct |
10 | Correct | 246 ms | 52672 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 24796 KB | Output is correct |
2 | Correct | 3 ms | 24796 KB | Output is correct |
3 | Correct | 3 ms | 24956 KB | Output is correct |
4 | Correct | 399 ms | 52952 KB | Output is correct |
5 | Correct | 339 ms | 53896 KB | Output is correct |
6 | Correct | 273 ms | 53924 KB | Output is correct |
7 | Correct | 309 ms | 53896 KB | Output is correct |
8 | Correct | 366 ms | 50956 KB | Output is correct |
9 | Correct | 316 ms | 50980 KB | Output is correct |
10 | Correct | 309 ms | 53092 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 24796 KB | Output is correct |
2 | Correct | 3 ms | 24796 KB | Output is correct |
3 | Correct | 3 ms | 24956 KB | Output is correct |
4 | Correct | 399 ms | 52952 KB | Output is correct |
5 | Correct | 339 ms | 53896 KB | Output is correct |
6 | Correct | 273 ms | 53924 KB | Output is correct |
7 | Correct | 309 ms | 53896 KB | Output is correct |
8 | Correct | 366 ms | 50956 KB | Output is correct |
9 | Correct | 316 ms | 50980 KB | Output is correct |
10 | Correct | 309 ms | 53092 KB | Output is correct |
11 | Correct | 36 ms | 25096 KB | Output is correct |
12 | Correct | 233 ms | 53096 KB | Output is correct |
13 | Correct | 383 ms | 51816 KB | Output is correct |
14 | Correct | 309 ms | 51968 KB | Output is correct |
15 | Correct | 326 ms | 52924 KB | Output is correct |
16 | Correct | 256 ms | 52948 KB | Output is correct |
17 | Correct | 313 ms | 52796 KB | Output is correct |
18 | Correct | 393 ms | 52480 KB | Output is correct |
19 | Correct | 339 ms | 52628 KB | Output is correct |
20 | Correct | 366 ms | 52664 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 569 ms | 64144 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24796 KB | Output is correct |
2 | Correct | 3 ms | 24796 KB | Output is correct |
3 | Correct | 0 ms | 24796 KB | Output is correct |
4 | Correct | 3 ms | 25060 KB | Output is correct |
5 | Correct | 303 ms | 63972 KB | Output is correct |
6 | Correct | 139 ms | 49484 KB | Output is correct |
7 | Correct | 296 ms | 50184 KB | Output is correct |
8 | Correct | 213 ms | 52140 KB | Output is correct |
9 | Correct | 283 ms | 50248 KB | Output is correct |
10 | Correct | 246 ms | 52672 KB | Output is correct |
11 | Incorrect | 3 ms | 25060 KB | Output isn't correct |
12 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 24796 KB | Output is correct |
2 | Correct | 3 ms | 24796 KB | Output is correct |
3 | Correct | 0 ms | 24796 KB | Output is correct |
4 | Correct | 3 ms | 25060 KB | Output is correct |
5 | Correct | 303 ms | 63972 KB | Output is correct |
6 | Correct | 139 ms | 49484 KB | Output is correct |
7 | Correct | 296 ms | 50184 KB | Output is correct |
8 | Correct | 213 ms | 52140 KB | Output is correct |
9 | Correct | 283 ms | 50248 KB | Output is correct |
10 | Correct | 246 ms | 52672 KB | Output is correct |
11 | Correct | 0 ms | 24796 KB | Output is correct |
12 | Correct | 3 ms | 24796 KB | Output is correct |
13 | Correct | 3 ms | 24956 KB | Output is correct |
14 | Correct | 399 ms | 52952 KB | Output is correct |
15 | Correct | 339 ms | 53896 KB | Output is correct |
16 | Correct | 273 ms | 53924 KB | Output is correct |
17 | Correct | 309 ms | 53896 KB | Output is correct |
18 | Correct | 366 ms | 50956 KB | Output is correct |
19 | Correct | 316 ms | 50980 KB | Output is correct |
20 | Correct | 309 ms | 53092 KB | Output is correct |
21 | Correct | 36 ms | 25096 KB | Output is correct |
22 | Correct | 233 ms | 53096 KB | Output is correct |
23 | Correct | 383 ms | 51816 KB | Output is correct |
24 | Correct | 309 ms | 51968 KB | Output is correct |
25 | Correct | 326 ms | 52924 KB | Output is correct |
26 | Correct | 256 ms | 52948 KB | Output is correct |
27 | Correct | 313 ms | 52796 KB | Output is correct |
28 | Correct | 393 ms | 52480 KB | Output is correct |
29 | Correct | 339 ms | 52628 KB | Output is correct |
30 | Correct | 366 ms | 52664 KB | Output is correct |
31 | Incorrect | 569 ms | 64144 KB | Output isn't correct |
32 | Halted | 0 ms | 0 KB | - |