제출 #895861

#제출 시각아이디문제언어결과실행 시간메모리
895861math_rabbit_1028Dynamic Diameter (CEOI19_diameter)C++14
컴파일 에러
0 ms0 KiB
include <bits/stdc++.h> using namespace std; typedef long long ll; typedef struct { int idx; ll val; } pil; const ll MOD = 998244353; int n, q; ll w; ll edges[101010][3]; vector<pil> adj[101010]; int ch[101010], sz[101010]; vector<int> child[101010]; int par[101010]; void get_sz(int v, int par = -1) { sz[v] = 1; for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i].idx; if (ch[u] == 1) continue; if (u == par) continue; get_sz(u, v); sz[v] += sz[u]; } } int get_cent(int tot, int v, int par = -1) { for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i].idx; if (ch[u] == 1) continue; if (u == par) continue; if (sz[u] * 2 > tot) return get_cent(tot, u, v); } return v; } void cent(int v, int tot) { get_sz(v); v = get_cent(tot, v); get_sz(v); ch[v] = 1; for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i].idx; if (ch[u] == 1) continue; par[u] = v; child[v].push_back(u); cent(u, sz[u]); } } int ord[202020], r = 0, in[101010], out[101010], depth[101010]; ll dis[101010]; void ett(int v, int par = -1) { ord[++r] = v; in[v] = r; for (int i = 0; i < adj[v].size(); i++) { int u = adj[v][i].idx; if (u == par) continue; dis[u] = dis[v] + adj[v][i].val; depth[u] = depth[v] + 1; ett(u, v); } out[v] = r; } struct maxseg { pil tree[808080]; ll lazy[808080]; pil mer(pil lt, pil rt) { if (lt.val > rt.val) return lt; if (lt.val < rt.val) return rt; if (lt.val == rt.val) { if (lt.idx > rt.idx) return lt; else return rt; } } void prop(int v) { tree[v].val += lazy[v]; lazy[2*v] += lazy[v]; lazy[2*v+1] += lazy[v]; lazy[v] = 0; } void init(int v, int st, int ed) { if (st == ed) { tree[v] = {ord[st], dis[ord[st]]}; lazy[v] = 0; return; } int mid = (st + ed) / 2; init(2*v, st, mid); init(2*v+1, mid+1, ed); tree[v] = mer(tree[2*v], tree[2*v+1]); } void upd(int v, int st, int ed, int lt, int rt, ll diff) { prop(v); if (lt <= st && ed <= rt) { lazy[v] = diff; prop(v); return; } if (st > rt || lt > ed) return; int mid = (st + ed) / 2; upd(2*v, st, mid, lt, rt, diff); upd(2*v+1, mid+1, ed, lt, rt, diff); tree[v] = mer(tree[2*v], tree[2*v+1]); } pil get(int v, int st, int ed, int lt, int rt) { prop(v); if (lt <= st && ed <= rt) return tree[v]; if (st > rt || lt > ed) return {-1, -1}; int mid = (st + ed) / 2; return mer(get(2*v, st, mid, lt, rt), get(2*v+1, mid+1, ed, lt, rt)); } } seg; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q >> w; for (int i = 1; i < n; i++) { int a, b; ll c; cin >> a >> b >> c; edges[i][0] = a; edges[i][1] = b; edges[i][2] = c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } //cent(1, n); ett(1); for (int i = 1; i < n; i++) { if (depth[edges[i][0]] > depth[edges[i][1]]) swap(edges[i][0], edges[i][1]); } seg.init(1, 1, n); ll last = 0; while (q--) { int d; ll e; cin >> d >> e; d = (d + last) % (n - 1) + 1; e = (e + last) % w; int v = edges[d][1]; seg.upd(1, 1, n, in[v], out[v], e - edges[d][2]); edges[d][2] = e; pil x = seg.get(1, 1, n, 1, n); pil y = seg.get(1, 1, n, 1, in[x.idx]-1); pil z = seg.get(1, 1, n, in[x.idx]+1, n); last = x.val + max(y.val, z.val); cout << last << "\n"; } return 0; }

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

diameter.cpp:1:1: error: 'include' does not name a type
    1 | include <bits/stdc++.h>
      | ^~~~~~~
diameter.cpp:13:1: error: 'vector' does not name a type
   13 | vector<pil> adj[101010];
      | ^~~~~~
diameter.cpp:15:1: error: 'vector' does not name a type
   15 | vector<int> child[101010];
      | ^~~~~~
diameter.cpp: In function 'void get_sz(int, int)':
diameter.cpp:20:25: error: 'adj' was not declared in this scope
   20 |     for (int i = 0; i < adj[v].size(); i++) {
      |                         ^~~
diameter.cpp: In function 'int get_cent(int, int, int)':
diameter.cpp:30:25: error: 'adj' was not declared in this scope
   30 |     for (int i = 0; i < adj[v].size(); i++) {
      |                         ^~~
diameter.cpp: In function 'void cent(int, int)':
diameter.cpp:45:25: error: 'adj' was not declared in this scope
   45 |     for (int i = 0; i < adj[v].size(); i++) {
      |                         ^~~
diameter.cpp:49:9: error: 'child' was not declared in this scope
   49 |         child[v].push_back(u);
      |         ^~~~~
diameter.cpp: In function 'void ett(int, int)':
diameter.cpp:58:25: error: 'adj' was not declared in this scope
   58 |     for (int i = 0; i < adj[v].size(); i++) {
      |                         ^~~
diameter.cpp: In function 'int main()':
diameter.cpp:124:5: error: 'ios_base' has not been declared
  124 |     ios_base::sync_with_stdio(false);
      |     ^~~~~~~~
diameter.cpp:125:5: error: 'cin' was not declared in this scope; did you mean 'in'?
  125 |     cin.tie(0);
      |     ^~~
      |     in
diameter.cpp:135:9: error: 'adj' was not declared in this scope
  135 |         adj[a].push_back({b, c});
      |         ^~~
diameter.cpp:142:54: error: 'swap' was not declared in this scope
  142 |         if (depth[edges[i][0]] > depth[edges[i][1]]) swap(edges[i][0], edges[i][1]);
      |                                                      ^~~~
diameter.cpp:160:24: error: 'max' was not declared in this scope
  160 |         last = x.val + max(y.val, z.val);
      |                        ^~~
diameter.cpp:161:9: error: 'cout' was not declared in this scope; did you mean 'out'?
  161 |         cout << last << "\n";
      |         ^~~~
      |         out
diameter.cpp: In member function 'pil maxseg::mer(pil, pil)':
diameter.cpp:79:5: warning: control reaches end of non-void function [-Wreturn-type]
   79 |     }
      |     ^