제출 #1246361

#제출 시각아이디문제언어결과실행 시간메모리
1246361KindaGoodGamesDynamic Diameter (CEOI19_diameter)C++20
0 / 100
119 ms22088 KiB
#pragma GCC optimize("O3, unroll-loops,Ofast") #include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define tiii tuple<int,int,int> int INF = numeric_limits<int>::max()/4; struct Value{ int ma = -INF; int ma2 = -INF; Value(){} Value(int a){ ma = a; } Value(int a, int b){ ma = a; ma2 = b; } void add(int v){ ma += v; ma2 += v; } }; Value comb(Value a, Value b){ vector<int> r = {a.ma,a.ma2,b.ma,b.ma2}; sort(r.rbegin(),r.rend()); return Value(r[0],r[1]); } struct SegmentTree{ vector<Value> S; vector<int> lazy; int len = 1; SegmentTree(int n){ while(len < n){ len <<= 1; } S.resize(2*len); lazy.resize(2*len); } void upd(int i, int v){ i += len; S[i] = Value(v); for(i /= 2; i > 0; i /= 2){ S[i] = comb(S[i*2], S[i*2+1]); } } void apply1(int i, int v){ S[i].add(v); lazy[i] += v; } void push(int i){ apply1(i*2+1, lazy[i]); apply1(i*2, lazy[i]); lazy[i] = 0; } Value query(int ql, int qr, int l = 0, int r = -2, int i = 1){ if(r == -2) r = len; if(ql <= l && r <= qr) { return S[i]; } if(r <= ql || qr <= l) { return Value(); } int mid = (l+r)/2; push(i); Value a = query(ql,qr,l,mid,i*2); Value b= query(ql,qr,mid,r,i*2+1); return comb(a,b); } void apply(int ql, int qr, int v, int l = 0, int r = -2, int i = 1){ if(r == -2) r = len; if(ql <= l && r <= qr) { apply1(i,v); return; } if(r <= ql || qr <= l) return; int mid = (l+r)/2; push(i); apply(ql,qr,v,l,mid,i*2);apply(ql,qr,v,mid,r,i*2+1); S[i] = comb(S[i*2], S[i*2+1]); } }; vector<int> val, cost, ftree; vector<int> par, sz, depth; vector<int> start, stop; vector<vector<pii>> adj; int timer = 0; void DFS(int v, int p, int d = 0, int len = 0, int f = -1){ start[v] = timer++; depth[v] = d; sz[v] = 1; par[v] = p; int h = -1; int s = -1; for(auto u : adj[v]){ if(u.first == p) continue; val[u.first] = len+u.second; cost[u.first] = u.second; int nf = -1; if(f == -1){ nf = u.second; } DFS(u.first,v, d+1, len+u.second, nf); sz[v] += sz[u.first]; } stop[v] = timer; } int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n,q,w; cin >> n >> q >> w; vector<tiii> edges(n-1); adj.resize(n); val.resize(n); par = sz = val = depth = cost=start=stop= vector<int>(n,-1); for(int i = 0; i < n-1; i++){ int a,b,c; cin >> a >> b >> c; a--;b--; edges[i] = {a,b,c}; adj[a].push_back({b,c}); adj[b].push_back({a,c}); } DFS(0,0); val[0] = 0; cost[0] = 0; SegmentTree seg(n); for(int i = 0; i < n; i++){ seg.upd(start[i],val[i]); } int last = 0; SegmentTree seg2(adj[0].size()); for(int i = 0; i < adj[0].size(); i++){ auto u = adj[0][i]; Value v = seg.query(start[u.first],stop[u.first]); seg2.upd(i,v.ma); } while(q--){ int d,e; cin >> d >> e; int edge = (last+d) % (n-1); int weight = (e+last)%w; int a,b,c; tie(a,b,c) = edges[edge]; if(depth[a] < depth[b]) swap(a,b); int diff = weight-c; seg.apply(start[a], stop[a], diff); edges[edge] = {a,b,weight}; cost[a] = weight; auto u = adj[0][ftree[a]]; seg2.upd(ftree[a], seg.query(start[u.first],stop[u.first]).ma); int ma = 0; for(int i = 0; i < 1; i++){ Value res = Value(); int rem = seg.query(start[i], start[i]+1).ma; int pv = max((res.ma+res.ma2) - (2*rem),res.ma - rem); if(pv > ma){ ma = max({ma, pv}); } } cout << ma << "\n"; last = ma; } }

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

diameter.cpp:1:46: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3, unroll-loops,Ofast")
      |                                              ^
diameter.cpp:15:11: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   15 |     Value(){}
      |           ^
diameter.cpp:16:16: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   16 |     Value(int a){
      |                ^
diameter.cpp:19:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   19 |     Value(int a, int b){
      |                       ^
diameter.cpp:24:19: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   24 |     void add(int v){
      |                   ^
diameter.cpp:30:28: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   30 | Value comb(Value a, Value b){
      |                            ^
diameter.cpp:40:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   40 |     SegmentTree(int n){
      |                      ^
diameter.cpp:49:26: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   49 |     void upd(int i, int v){
      |                          ^
diameter.cpp:59:29: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   59 |     void apply1(int i, int v){
      |                             ^
diameter.cpp:64:20: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   64 |     void push(int i){
      |                    ^
diameter.cpp:72:65: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   72 |     Value query(int ql, int qr, int l = 0, int r = -2, int i = 1){
      |                                                                 ^
diameter.cpp:91:71: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   91 |     void apply(int ql, int qr, int v, int l = 0, int r = -2, int i = 1){
      |                                                                       ^
diameter.cpp:114:58: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  114 | void DFS(int v, int p, int d = 0, int len = 0, int f = -1){
      |                                                          ^
diameter.cpp:140:14: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
  140 | int32_t main(){
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...