제출 #201694

#제출 시각아이디문제언어결과실행 시간메모리
201694georgerapeanuDynamic Diameter (CEOI19_diameter)C++11
49 / 100
5056 ms161612 KiB
#pragma comment(linker, "/stack:200000000") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <cstdio> #include <algorithm> #include <vector> #include <set> using namespace std; const int NMAX = 1e5; class SegTree{ public: int n; vector <long long> aint; vector <long long> lazy; void propag(int nod,int st,int dr){ if(lazy[nod] == 0 || st == dr){ return ; } aint[nod * 2] += lazy[nod]; lazy[nod * 2] += lazy[nod]; aint[nod * 2 + 1] += lazy[nod]; lazy[nod * 2 + 1] += lazy[nod]; lazy[nod] = 0; } void update(int nod,int st,int dr,int l,int r,long long delta){ propag(nod,st,dr); if(dr < l || st > r){ return ; } if(l <= st && dr <= r){ aint[nod] += delta; lazy[nod] += delta; return ; } int mid = (st + dr) / 2; update(nod * 2,st,mid,l,r,delta); update(nod * 2 + 1,mid + 1,dr,l,r,delta); aint[nod] = max(aint[nod * 2],aint[nod * 2 + 1]); } public: SegTree(int n){ this->n = n; aint = vector<long long>(4 * n + 1,0); lazy = vector<long long>(4 * n + 1,0); } inline void update(int l,int r,long long val){ update(1,1,n,l,r,val); } inline long long query(){ return aint[1]; } }; struct edge_t{ int u,v; long long cost; inline int other(int x){ return u ^ v ^ x; } }; struct data_t{ int centroid; int tree_id; int st,dr; }; int n,q; long long w; bool viz[NMAX + 5]; int weight[NMAX + 5]; vector<int> graph[NMAX + 5]; edge_t edge[NMAX + 5]; vector<data_t> stuff[NMAX + 5]; const int LEN = 1 << 12; char buff[LEN]; int ind = LEN - 1; int i32(){ int ans = 0; while(buff[ind] < '0' || buff[ind] > '9'){ if(++ind >= LEN){ ind = 0; fread(buff,1,LEN,stdin); } } while(!(buff[ind] < '0' || buff[ind] > '9')){ ans = ans * 10 + buff[ind] - '0'; if(++ind >= LEN){ ind = 0; fread(buff,1,LEN,stdin); } } return ans; } long long i64(){ long long ans = 0; while(buff[ind] < '0' || buff[ind] > '9'){ if(++ind >= LEN){ ind = 0; fread(buff,1,LEN,stdin); } } while(!(buff[ind] < '0' || buff[ind] > '9')){ ans = ans * 10 + buff[ind] - '0'; if(++ind >= LEN){ ind = 0; fread(buff,1,LEN,stdin); } } return ans; } class RootSolver{ public: vector<SegTree> trees; set<pair<long long,int> > answer; int lst; void dfs(int nod,int tata,int centroid,int id,int edge_id){ weight[nod] = 1; data_t tmp; lst++; tmp.centroid = centroid; tmp.tree_id = id; tmp.st = lst; for(auto it:graph[nod]){ if(viz[edge[it].other(nod)] == true || edge[it].other(nod) == tata){ continue; } dfs(edge[it].other(nod),nod,centroid,id,it); weight[nod] += weight[edge[it].other(nod)]; } tmp.dr = lst; stuff[edge_id].push_back(tmp); } public: RootSolver(){ } RootSolver(int root){ for(auto it:graph[root]){ if(viz[edge[it].other(root)] == false){ lst = 0; dfs(edge[it].other(root),root,root,trees.size(),it); answer.insert({0,trees.size()}); trees.push_back(SegTree(weight[edge[it].other(root)])); } } } inline void update(const data_t &tmp,long long delta){ answer.erase({trees[tmp.tree_id].query(),tmp.tree_id}); trees[tmp.tree_id].update(tmp.st,tmp.dr,delta); answer.insert({trees[tmp.tree_id].query(),tmp.tree_id}); } inline long long query(){ if((int)answer.size() == 0){ return 0; } else if((int)answer.size() == 1){ return answer.rbegin()->first; } else{ return answer.rbegin()->first + (next(answer.rbegin())->first); } } }; class Centroid{ public: int root; vector<RootSolver> chestie; set<pair<long long,int> > answers; void dfs(int nod,int tata){ weight[nod] = 1; for(auto it:graph[nod]){ if(edge[it].other(nod) == tata || viz[edge[it].other(nod)] == true){ continue; } dfs(edge[it].other(nod),nod); weight[nod] += weight[edge[it].other(nod)]; } } int centroid(int nod){ dfs(nod,0); int total_weight = weight[nod]; int root = nod; while(true){ int bst = -1; for(auto it:graph[root]){ if(viz[edge[it].other(root)] == true || edge[it].other(root) == nod){ continue; } if(bst == -1 || weight[edge[it].other(root)] > weight[bst]){ bst = edge[it].other(root); } } if(bst != -1 && weight[bst] * 2 > total_weight){ nod = root; root = bst; } else{ break; } } viz[root] = true; chestie[root] = RootSolver(root); answers.insert({0,root}); for(auto it:graph[root]){ if(viz[edge[it].other(root)] == false){ int tmp = centroid(edge[it].other(root)); } } return root; } public: Centroid(int n){ this->chestie = vector<RootSolver>(n + 1,RootSolver()); this->root = centroid(1); } inline void update(const data_t &tmp,long long delta){ answers.erase({chestie[tmp.centroid].query(),tmp.centroid}); chestie[tmp.centroid].update(tmp,delta); answers.insert({chestie[tmp.centroid].query(),tmp.centroid}); } inline long long query(){ return answers.rbegin()->first; } }; int main(){ n = i32(); q = i32(); w = i64(); for(int i = 1;i <= n;i++){ stuff[i].reserve(20); } for(int i = 1;i < n;i++){ edge[i].u = i32(); edge[i].v = i32(); edge[i].cost = i64(); graph[edge[i].u].push_back(i); graph[edge[i].v].push_back(i); } long long last = 0; Centroid a(n); for(int i = 1;i < n;i++){ for(auto it:stuff[i]){ a.update(it,edge[i].cost); } } while(q--){ int d; long long e; d = i32(); e = i64(); d = (d + last) % (n - 1) + 1; e = (e + last) % w; for(auto it:stuff[d]){ a.update(it,e - edge[d].cost); } edge[d].cost = e; last = a.query(); printf("%lld\n",last); } return 0; }

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

diameter.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:200000000")
 
diameter.cpp: In member function 'int Centroid::centroid(int)':
diameter.cpp:248:21: warning: unused variable 'tmp' [-Wunused-variable]
                 int tmp = centroid(edge[it].other(root));
                     ^~~
diameter.cpp: In function 'int i32()':
diameter.cpp:103:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
diameter.cpp:111:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
diameter.cpp: In function 'long long int i64()':
diameter.cpp:123:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
diameter.cpp:131:18: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
             fread(buff,1,LEN,stdin);
             ~~~~~^~~~~~~~~~~~~~~~~~
#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...