제출 #40999

#제출 시각아이디문제언어결과실행 시간메모리
40999DoanPhuDuc공장들 (JOI14_factories)C++98
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> #define FOR(x, a, b) for (int x = a; x <= b; ++x) #define FOD(x, a, b) for (int x = a; x >= b; --x) #define REP(x, a, b) for (int x = a; x < b; ++x) #define DEBUG(X) { cout << #X << " = " << X << endl; } #define PR(A, n) { cout << #A << " = "; FOR(_, 1, n) cout << A[_] << " "; cout << endl; } #define PR0(A, n) { cout << #A << " = "; REP(_, 0, n) cout << A[_] << " "; cout << endl; } using namespace std; typedef long long LL; typedef pair <int, int> II; const int N = 5e5 + 10; const LL INF = (LL)1e18; const int LG = 19; int n, s, t, q; int h[N], a[N], b[N], e[N]; int p[N][LG + 2]; LL f[N], d[N]; vector <II> adj[N]; struct CD { int cPar[N], c[N]; void Init() { memset(cPar, -1, sizeof cPar); DFS(1); Centroid(1, -1, c[1], -2); } void DFS(int u, int par = -1) { c[u] = 1; REP(k, 0, adj[u].size()) { int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue; DFS(v, u); c[u] += c[v]; } } void Centroid(int u, int par, int sz, int preC) { REP(k, 0, adj[u].size()) { int v = adj[u][k].first; if (v == par || cPar[v] != -1) continue; if (c[v] * 2 > sz) { Centroid(v, u, sz, preC); return; } } cPar[u] = preC; REP(k, 0, adj[u].size()) { int v = adj[u][k].first; if (cPar[v] != -1) continue; DFS(v, u); Centroid(v, u, c[v], u); } } } CD; void DFS(int u) { REP(k, 0, adj[u].size()) { int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u][0]) continue; p[v][0] = u; d[v] = d[u] + w; h[v] = h[u] + 1; DFS(v); } } void InitLCA() { for (int j = 1; 1 << j <= n; ++j) FOR(i, 1, n) p[i][j] = p[p[i][j - 1]][j - 1]; } int LCA(int u, int v) { if (h[u] < h[v]) swap(u, v); FOD(i, 19, 0) if (h[u] - (1 << i) >= h[v]) u = p[u][i]; if (u == v) return u; FOD(i, 19, 0) if (p[u][i] != p[v][i]) { u = p[u][i]; v = p[v][i]; } return p[u][0]; } LL Dist(int u, int v) { int w = LCA(u, v); return d[u] + d[v] - 2LL * d[w]; } void Init(int N, int A[], int B[], int D[]) { n = N; REP(i, 0, n - 1) { int u = A[i], v = B[i], w = D[i]; ++u; ++v; adj[u].push_back(II(v, w)); adj[v].push_back(II(u, w)); } FOR(i, 1, n) f[i] = INF; DFS(1); InitLCA(); CD.Init(); } void Update(int u) { int x = u; while (x != -2) { f[x] = min(f[x], Dist(x, u)); x = CD.cPar[x]; } } void Assign(int u, LL v) { int x = u; while (x != -2) { f[x] = v; x = CD.cPar[x]; } } LL Query(int u) { int x = u; LL ans = INF; while (x != -2) { ans = min(ans, f[x] + Dist(x, u)); x = CD.cPar[x]; } return ans; } long long Query(int S, int X[], int T, int Y[]) { s = S; t = T; LL ans = INF; REP(i, 0, s) ++X[i]; REP(i, 0, t) ++Y[i]; REP(i, 0, s) Update(X[i]); REP(i, 0, t) ans = min(ans, Query(Y[i])); REP(i, 0, s) Assign(X[i], INF); return ans; } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // LOCAL scanf("%d%d", &n, &q); FOR(i, 0, n - 2) scanf("%d%d%d", &a[i], &b[i], &e[i]); Init(n, a, b, e); while (q--) { int s, t; scanf("%d%d", &s, &t); REP(i, 0, s) scanf("%d", &a[i]); REP(i, 0, t) scanf("%d", &b[i]); cout << Query(s, a, t, b) << endl; } return 0; }

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

factories.cpp: In member function 'void CD::DFS(int, int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:36:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[u].size()) {
         ^
factories.cpp: In member function 'void CD::Centroid(int, int, int, int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:43:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[u].size()) {
         ^
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:51:9: note: in expansion of macro 'REP'
         REP(k, 0, adj[u].size()) {
         ^
factories.cpp: In function 'void DFS(int)':
factories.cpp:5:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(x, a, b) for (int x = a; x < b; ++x)
                                        ^
factories.cpp:60:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
factories.cpp: In function 'int main()':
factories.cpp:145:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
                          ^
factories.cpp:146:58: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 0, n - 2) scanf("%d%d%d", &a[i], &b[i], &e[i]);
                                                          ^
factories.cpp:149:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int s, t; scanf("%d%d", &s, &t);
                                        ^
factories.cpp:150:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         REP(i, 0, s) scanf("%d", &a[i]);
                                        ^
factories.cpp:151:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         REP(i, 0, t) scanf("%d", &b[i]);
                                        ^
/tmp/ccEB1fpV.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccE57t0O.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status