이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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: In member function 'int Centroid::centroid(int)':
diameter.cpp:244:21: warning: unused variable 'tmp' [-Wunused-variable]
int tmp = centroid(edge[it].other(root));
^~~
diameter.cpp: In function 'int i32()':
diameter.cpp:99: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:107: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:119: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:127: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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |