제출 #40973

#제출 시각아이디문제언어결과실행 시간메모리
40973DoanPhuDuc공장들 (JOI14_factories)C++98
0 / 100
6069 ms62616 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 = 1e5 + 10; const LL INF = (LL)1e18; int n, timer = 0, q, s, t; int sz[N], x[N], y[N], c[N], p[N], V[N], headChain[N]; int a[N], b[N], e[N]; LL d[N]; vector <II> adj[N]; struct Node { LL s0, s1, s2; Node () {} Node (LL s0, LL s1, LL s2) : s0(s0), s1(s1), s2(s2) {} }; struct SegmentTree { #define m ((l + r) >> 1) Node st[4 * N]; LL lp[4 * N]; bool rst[4 * N]; void Merge(int k) { st[k].s0 = min(st[k << 1].s0, st[k << 1 | 1].s0); st[k].s1 = min(st[k << 1].s1, st[k << 1 | 1].s1); st[k].s2 = min(st[k << 1].s2, st[k << 1 | 1].s2); } void Build(int k, int l, int r) { lp[k] = INF; if (l == r) { int u = V[l]; st[k] = Node(-2LL * d[u], INF, INF); return; } Build(k << 1, l, m); Build(k << 1 | 1, m + 1, r); Merge(k); } void RS(int k) { if (rst[k] == false) return; rst[k] = false; rst[k << 1] = true; rst[k << 1 | 1] = true; st[k << 1].s1 = st[k << 1].s2 = INF; st[k << 1 | 1].s1 = st[k << 1 | 1].s2 = INF; lp[k << 1] = INF; lp[k << 1 | 1] = INF; } void Propagate(int k) { if (lp[k] >= INF) return; LL v = lp[k]; lp[k] = INF; lp[k << 1] = min(lp[k << 1], v); lp[k << 1 | 1] = min(lp[k << 1 | 1], v); st[k << 1].s1 = min(st[k << 1].s1, v); st[k << 1 | 1].s1 = min(st[k << 1 | 1].s1, v); st[k << 1].s2 = min(st[k << 1].s2, st[k << 1].s0 + v); st[k << 1 | 1].s2 = min(st[k << 1 | 1].s2, st[k << 1 | 1].s0 + v); } void Update(int k, int l, int r, int i, int j, LL v) { if (l > j || r < i) return; if (i <= l && r <= j) { lp[k] = min(lp[k], v); st[k].s1 = min(st[k].s1, v); st[k].s2 = min(st[k].s2, st[k].s0 + v); return; } RS(k); Propagate(k); Update(k << 1, l, m, i, j, v); Update(k << 1 | 1, m + 1, r, i, j, v); Merge(k); } LL Query(int k, int l, int r, int i, int j) { if (l > j || r < i) return INF; if (i <= l && r <= j) return st[k].s2; RS(k); Propagate(k); LL ans = min(Query(k << 1, l, m, i, j), Query(k << 1 | 1, m + 1, r, i, j)); Merge(k); return ans; } void Reset(int k, int l, int r, int i, int j) { if (l > j || r < i) return; if (i <= l && r <= j) { rst[k] = true; lp[k] = INF; st[k].s1 = st[k].s2 = INF; return; } RS(k); Reset(k << 1, l, m, i, j); Reset(k << 1 | 1, m + 1, r, i, j); Merge(k); } #undef m } ST; void DFS(int u) { c[u] = 1; REP(k, 0, adj[u].size()) { int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u]) continue; p[v] = u; d[v] = d[u] + w; DFS(v); c[v] += c[u]; } } void HLD(int u, int par) { sz[par]++; x[u] = ++timer; V[timer] = u; headChain[u] = par; int vtx = 0; REP(k, 0, adj[u].size()) { int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u]) continue; if (vtx == 0 || c[vtx] < c[v]) vtx = v; } if (vtx != 0) HLD(vtx, par); REP(k, 0, adj[u].size()) { int v = adj[u][k].first; if (v == p[u] || v == vtx) continue; HLD(v, v); } y[u] = timer; } 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)); } DFS(1); HLD(1, 1); ST.Build(1, 1, n); } void Update(int u, LL v) { int a = 1; int uChain = headChain[u], aChain = headChain[a]; while (true) { if (aChain == uChain) { ST.Update(1, 1, n, x[a], x[u], v); break; } ST.Update(1, 1, n, x[uChain], x[u], v); u = uChain; u = p[u]; uChain = headChain[u]; } } void Reset(int u) { int a = 1; int uChain = headChain[u], aChain = headChain[a]; while (true) { if (aChain == uChain) { ST.Reset(1, 1, n, x[a], x[u]); break; } ST.Reset(1, 1, n, x[uChain], x[u]); u = uChain; u = p[u]; uChain = headChain[u]; } } LL Query(int u) { LL w = d[u]; int a = 1; int uChain = headChain[u], aChain = headChain[a]; LL ans = INF; while (true) { if (aChain == uChain) { ans = min(ans, ST.Query(1, 1, n, x[a], x[u])); break; } ans = min(ans, ST.Query(1, 1, n, x[uChain], x[u])); u = uChain; u = p[u]; uChain = headChain[u]; } return ans + w; } long long Query(int S, int X[], int T, int Y[]) { s = S; t = T; REP(i, 0, s) { int u = X[i]; ++u; Update(u, d[u]); } LL ans = INF; REP(i, 0, t) { int u = Y[i]; ++u; ans = min(ans, Query(u)); } REP(i, 0, s) { int u = X[i]; ++u; Reset(u); } 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 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:111:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
factories.cpp: In function 'void HLD(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:123:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
factories.cpp:124:34: warning: unused variable 'w' [-Wunused-variable]
         int v = adj[u][k].first, w = adj[u][k].second; if (v == p[u]) continue;
                                  ^
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:128:5: note: in expansion of macro 'REP'
     REP(k, 0, adj[u].size()) {
     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...