제출 #495558

#제출 시각아이디문제언어결과실행 시간메모리
495558K4YAN공장들 (JOI14_factories)C++17
컴파일 에러
0 ms0 KiB
//Be Name Khoda #include<bits/stdc++.h> #pragma GCC optimize("Ofast,unroll-loops") using namespace std; #define ll long long #define all(x) x.begin(), x.end() #define pii pair<int, int> #define pll pair<ll, ll> const ll mxn = 5e5 + 16, INF = 1e15 + 32; ll n, m, q, w, ans; ll st[mxn], fn[mxn], h[mxn], dis[mxn], c[mxn], dp[mxn][3], par[mxn][20]; vector<ll> f, g; vector<pll> adj[mxn], G[mxn]; set<ll> s; bitset<mxn> mark; void DFS(int v) { mark.set(v); st[v] = q++, fn[v] = q, h[v] = w++; for(int i = 1; i < 20; i++) { par[v][i] = par[par[v][i - 1]][i - 1]; } for(auto u : adj[v]) { if(!mark[u.first]) { par[u.first][0] = v; dis[u.first] = h[v] + u.second; DFS(u.first); fn[v] = fn[u.first]; } } w--; } inline void Init(int N, int A[], int B[], int D[]) { n = N; for(int i = 0; i < n - 1; i++) { adj[A[i]].push_back({B[i], D[i]}); adj[B[i]].push_back({A[i], D[i]}); } DFS(0); mark.reset(); } inline void clr() { for(auto u : f) { c[u] = 0; } f.clear(); return; } bool comp(int a, int b) { return st[a] < st[b]; } ll find_lca(ll v, ll u) { if(v == u) return v; if(h[v] > h[u]) { swap(v, u); } for(int i = 19; i > -1; i--) { if(h[u] - (1LL << i) < h[v]) continue; u = par[u][i]; } if(v == u) return v; for(int i = 19; i > -1; i--) { if(par[u][i] != par[v][i]) { u = par[u][i], v = par[v][i]; } } return par[v][0]; } inline void build_Graph() { stack<ll> st; st.push(g[0]); dp[g[0]][0] = dp[g[0]][1] = dp[g[0]][2] = INF; for(int i = 1; i < int(g.size()); i++) { while(fn[st.top()] < fn[f[i]]) st.pop(); dp[g[i]][0] = dp[g[i]][1] = dp[g[i]][2] = INF; G[st.top()].push_back({f[i], dis[f[i]] - dis[st.top()]}); } } void solve_dp(int v) { dp[v][c[v] % 2] = 0; for(auto u : G[v]) { solve_dp(u.first); dp[v][2] = min(dp[v][2], dp[u.first][2]); dp[v][1] = min(dp[v][1], dp[u.first][1] + u.second); dp[v][0] = min(dp[v][0], dp[u.first][0] + u.second); } dp[v][2] = min(dp[v][2], dp[v][1] + dp[v][0]); return; } inline ll Query(int S, int X[], int T, int Y[]) { for(auto u : g) { G[u].clear(); } clr(); s.clear(), f.clear(), g.clear(); for(int i = 0; i < S; i++) { c[X[i]] = 1; f.push_back(X[i]); s.insert(X[i]); } for(int i = 0; i < T; i++) { c[Y[i]] += 2; f.push_back(Y[i]); s.insert(Y[i]); if(c[Y[i]] == 3) { return 0; } } sort(all(f), comp); g = f; for(int i = 0; i < int(f.size()) - 1; i++) { w = find_lca(f[i], f[i + 1]); if(!s.count(w)) { s.insert(w); g.push_back(w); } } sort(all(g), comp); build_Graph(); solve_dp(g[0]); ans = dp[g[0]][2]; return ans; }

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

/usr/bin/ld: /tmp/ccwOEIDT.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status