제출 #482008

#제출 시각아이디문제언어결과실행 시간메모리
482008MilosMilutinovic공장들 (JOI14_factories)C++14
100 / 100
5238 ms414512 KiB
#include <bits/stdc++.h> #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i)) #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i)) #define pb push_back #define xx first #define yy second #define pii pair<int,int> #define ll long long using namespace std; int n; int sajz[500005]; int par[500005][23]; vector<pii> graf[500005]; bool was[500005]; vector<pair<int, ll>> cale[500005]; int dub[500005]; ll dep[500005]; void dfs(int u, int p){ dub[u] = dub[p] + 1; par[u][0] = p; ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1]; for(auto c:graf[u]){ if(c.xx != p){ dep[c.xx] = dep[u] + c.yy; dfs(c.xx, u); } } } int lca(int u, int v){ if(dub[u] < dub[v])swap(u, v); fb(i,22,0){ if(dub[par[u][i]] >= dub[v])u = par[u][i]; } //cout << u << " " << v << "\n"; assert(dub[u] == dub[v]); fb(i,22,0){ if(par[u][i] != par[v][i]){ u = par[u][i]; v = par[v][i]; } } if(u != v){ u = par[u][0]; v = par[v][0]; } assert(u == v); return u; } ll dist(int u, int v){ return dep[u] + dep[v] - 2 * dep[lca(u, v)]; } void dfs1(int u, int p){ sajz[u] = 1; for(auto c:graf[u]){ if(c.xx == p || was[c.xx]) { continue; } dfs1(c.xx, u); sajz[u] += sajz[c.xx]; } } int dfs2(int u, int p, int n){ for(auto c:graf[u]){ if(!was[c.xx] && c.xx != p && sajz[c.xx] * 2 >= n) { return dfs2(c.xx, u, n); } } return u; } int findcen(int u){ dfs1(u, u); return dfs2(u, u, sajz[u]); } void solve(int u, int p, int st, ll s){ cale[u].pb({st,s}); for(auto c:graf[u]){ if(c.xx != p && !was[c.xx]){ solve(c.xx, u, st, s + c.yy); } } } void decomp(int u) { u = findcen(u); solve(u, u, u, 0); was[u] = true; for(auto c:graf[u]){ if(!was[c.xx])decomp(c.xx); } } ll mn[500005]; void Init(int N, int* A, int* B, int* D){ n = N; ff(i,0,n-2){ A[i]++; B[i]++; graf[A[i]].pb({B[i], D[i]}); graf[B[i]].pb({A[i], D[i]}); } dfs(1, 0); decomp(1); // ff(i,1,n) assert((int) cale[i].size() <= 50); ff(i,1,n)mn[i] = 1e18; } ll Query(int S, int* X, int T, int* Y){ ll ans = 1e18; ff(i,0,S-1)X[i]++; ff(i,0,T-1)Y[i]++; //ff(i,0,S-1) ff(j,0,T-1) ans = min(ans, dist(X[i], Y[j])); vector<int> cv; ff(i,0,S-1){ assert(cale[i].size() <= 40); for(auto c:cale[X[i]]){ mn[c.xx] = min(mn[c.xx], c.yy); cv.pb(c.xx); } } ff(i,0,T-1){ for(auto c:cale[Y[i]]){ ans = min(ans, mn[c.xx] + c.yy); } } for(auto c:cv)mn[c] = 1e18; return ans; }

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

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:24:5: note: in expansion of macro 'ff'
   24 |     ff(i,1,22) par[u][i] = par[par[u][i - 1]][i - 1];
      |     ^~
factories.cpp: In function 'int lca(int, int)':
factories.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
factories.cpp:35:5: note: in expansion of macro 'fb'
   35 |     fb(i,22,0){
      |     ^~
factories.cpp:3:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    3 | #define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
      |                           ^
factories.cpp:40:5: note: in expansion of macro 'fb'
   40 |     fb(i,22,0){
      |     ^~
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:105:5: note: in expansion of macro 'ff'
  105 |     ff(i,0,n-2){
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:114:5: note: in expansion of macro 'ff'
  114 |     ff(i,1,n)mn[i] = 1e18;
      |     ^~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:119:5: note: in expansion of macro 'ff'
  119 |     ff(i,0,S-1)X[i]++;
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:120:5: note: in expansion of macro 'ff'
  120 |     ff(i,0,T-1)Y[i]++;
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:123:5: note: in expansion of macro 'ff'
  123 |     ff(i,0,S-1){
      |     ^~
factories.cpp:2:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    2 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
factories.cpp:130:5: note: in expansion of macro 'ff'
  130 |     ff(i,0,T-1){
      |     ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...