Submission #1048026

#TimeUsernameProblemLanguageResultExecution timeMemory
1048026beaconmcFactories (JOI14_factories)C++14
33 / 100
8015 ms337552 KiB
#include "factories.h" #include <bits/stdc++.h> typedef long long ll; #define FOR(i,x,y) for(ll i=x; i<y; i++) #define FORNEG(i,x,y) for(ll i=x; i>y; i--) using namespace std; const ll INF = 1000000000000000; vector<vector<ll>> edges[500005]; ll ancc[500005][30]; ll par[500005]; ll depth[500005]; ll realdepth[500005]; ll tin[500005]; ll timer = 0; ll anc(ll a, ll x){ if (a==0) return 0; if (x==0) return par[a]; if (ancc[a][x] != -1) return ancc[a][x]; return ancc[a][x] = anc(anc(a, x-1), x-1); } ll lca(ll a, ll b){ if (depth[a] < depth[b]) swap(a,b); FORNEG(i,29,-1) if (depth[anc(a,i)] >= depth[b]) a = anc(a,i); if (a==b) return a; FORNEG(i,29,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i); return par[a]; } void dfs(ll a, ll p, ll d, ll dd){ tin[a] = timer++; par[a] = p; depth[a] = d; realdepth[a] = dd; for (auto&i : edges[a]){ if (i[0] != p) dfs(i[0], a, d+1, dd+i[1]); } } void Init(int N, int A[], int B[], int D[]) { FOR(i,0,500005) edges[i].clear(), par[i] = -1, depth[i] = 0, realdepth[i] = -1; FOR(i,0,500005) FOR(j,0,30) ancc[i][j] = -1; FOR(i,0,N){ edges[A[i]].push_back({B[i], D[i]}); edges[B[i]].push_back({A[i], D[i]}); } dfs(0, -1, 0,0); } ll mina[500005]; ll minb[500005]; vector<vector<ll>> vtree[500005]; void dp(ll a){ for (auto&i : vtree[a]){ dp(i[0]); mina[a] = min(mina[a], mina[i[0]] + i[1]); minb[a] = min(minb[a], minb[i[0]] + i[1]); } } long long Query(int S, int X[], int T, int Y[]) { vector<vector<ll>> stuff; FOR(i,0,S) stuff.push_back({tin[X[i]],X[i]}); FOR(i,0,T) stuff.push_back({tin[Y[i]], Y[i]}); sort(stuff.begin(), stuff.end()); set<vector<ll>> stuff2; FOR(i,1,stuff.size()){ stuff2.insert({tin[lca(stuff[i][1], stuff[i-1][1])], lca(stuff[i][1], stuff[i-1][1])}); } if (stuff.size()){ ll temp = lca(stuff[0][1], stuff[stuff.size()-1][1]); stuff2.insert({tin[temp], temp}); } for (auto&i : stuff) stuff2.insert(i); vector<ll> stack; for (auto&i : stuff2) mina[i[1]] = INF, minb[i[1]] = INF, vtree[i[1]].clear(); FOR(i,0,S) mina[X[i]] = 0; FOR(i,0,T) minb[Y[i]] = 0; for (auto&i : stuff2){ while (stack.size() && lca(stack[stack.size()-1], i[1])!= stack[stack.size()-1])stack.pop_back(); if (stack.size()) vtree[stack[stack.size()-1]].push_back({i[1], realdepth[i[1]] - realdepth[stack[stack.size()-1]]}); stack.push_back(i[1]); } dp((*stuff2.begin())[1]); ll ans = INF; for (auto&i : stuff2) ans = min(ans, mina[i[1]] + minb[i[1]]); return ans; }

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:6:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
   76 |   FOR(i,1,stuff.size()){
      |       ~~~~~~~~~~~~~~~~           
factories.cpp:76:3: note: in expansion of macro 'FOR'
   76 |   FOR(i,1,stuff.size()){
      |   ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...