제출 #567678

#제출 시각아이디문제언어결과실행 시간메모리
567678hhhhaura자매 도시 (APIO20_swap)C++14
0 / 100
703 ms524288 KiB
#define wiwihorz #include "swap.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC target("sse") #pragma loop-opt(on) #define rep(i, a, b) for(int i = a; i <= b; i ++) #define rrep(i, a, b) for(int i = b; i >= a; i --) #define all(x) x.begin(), x.end() #define ll long long int #define pii pair<int, int> #define INF 2000000000 using namespace std; #ifdef wiwihorz #define print(a...)cerr<<"Line "<<__LINE__<<":",kout("["+string(#a)+"] = ", a) void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; } void kout() { cerr << endl; } template<class T1,class ... T2>void kout(T1 a,T2 ... e){cerr<<a<<" ",kout(e...);} #else #define print(...) 0 #define vprint(...) 0 #endif #define x first #define y second vector<vector<int>> ac, mx, mn; vector<vector<pii>> v, mp; vector<int> dep; int lg; void dfs(int x, int par, int d, int es, int val) { ac[0][x] = par; mx[0][x] = es; mn[0][x] = val; dep[x] = d; vector<pii> tp; for(auto i : mp[x]) tp.push_back({i.y, i.x}); sort(all(tp)); rep(i, 0, min(signed(tp.size()), 3) - 1) v[x][i] = tp[i]; for(auto i : mp[x]) if(i.x != par) { int ii = 0; while(ii < 3 && (v[x][ii].y == i.x || v[x][ii].y == par)) ii++; assert(ii < 3); dfs(i.x, x, d + 1, i.y, v[x][ii].x); } } int LCA(int a, int b) { if(dep[a] < dep[b]) swap(a, b); int need = dep[a] - dep[b]; rep(i, 0, lg) if((need >> i) & 1) { a = ac[i][a]; } if(a == b) return a; rrep(i, 0, lg) if(ac[i][a] != ac[i][b]) { a = ac[i][a]; b = ac[i][b]; } return ac[0][a]; } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { lg = 31 - __builtin_clz(N); mp.assign(N, vector<pii>()); ac.assign(lg + 1, vector<int>(N, 0)); mx.assign(lg + 1, vector<int>(N, 0)); mn.assign(lg + 1, vector<int>(N, INF)); v.assign(N, vector<pii>(3, {INF, -1})); dep.assign(N, 0); rep(i, 0, M - 1) { mp[U[i]].push_back({V[i], W[i]}); mp[V[i]].push_back({U[i], W[i]}); } dfs(0, 0, 0, 0, INF); rep(i, 1, lg) rep(j, 0, N - 1) { ac[i][j] = ac[i - 1][ac[i - 1][j]]; mx[i][j] = max(mx[i - 1][j], mx[i - 1][ac[i - 1][j]]); mn[i][j] = min(mn[i - 1][j], mn[i - 1][ac[i - 1][j]]); } return; } int go(int a, int x, int tp) { if(tp == 1) { int ans = 0; if(x > 0) rep(i, 0, lg) if((x >> i) & 1) { ans = max(ans, mx[i][a]); a = ac[i][a]; } return ans; } else { int ans = INF; if(x > 0) rep(i, 0, lg) if((x >> i) & 1) { ans = min(ans, mn[i][a]); a = ac[i][a]; } return ans; } } int getMinimumFuelCapacity(int X, int Y) { if(dep[X] < dep[Y]) swap(X, Y); int lca = LCA(X, Y); if(lca == Y) { int need = dep[X] - dep[Y]; int L = go(X, need, 1); int R = go(X, need - 1, 0); return max(L, R) == INF ? -1 : max(L, R); } else { int l = dep[X] - dep[lca]; int r = dep[Y] - dep[lca]; int L = max(go(X, l, 1), go(Y, r, 1)); int R = min(go(X, l - 1, 0), go(Y, r - 1, 0)); int ii = 0, x = X, y = Y; rep(i, 0, lg) if(((l - 1) >> i) & 1) x = ac[i][x]; rep(i, 0, lg) if(((r - 1) >> i) & 1) y = ac[i][y]; while(ii < 3 && (v[lca][ii].y == x || v[lca][ii].y == y)) ii ++; R = min(R, v[lca][ii].x); return max(L, R) == INF ? -1 : max(L, R); } }

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

swap.cpp:6: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    6 | #pragma loop-opt(on)
      | 
swap.cpp:16:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |             ^~~~
swap.cpp:16:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   16 | void vprint(auto L,auto R){while(L<R)cerr<<*L<<" \n"[next(L) == R], ++L; }
      |                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...