oj.uz

답안 #540661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
540661 2022-03-21T10:49:18 Z jamezzz Dynamic Diameter (CEOI19_diameter) C++17
36 / 100
 5000 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 2023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef pair<ll,int> li;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 100005

struct edge{
	int u,v;ll w;
	vector<int> comp;
	vector<ii> range;
};

struct node{
	int s,e,m;
	li v;ll lz;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;lz=0;v={0,s};
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		v.fi+=lz;
		if(s!=e)l->lz+=lz,r->lz+=lz;
		lz=0;
	}
	void up(int x,int y,ll nv){
		if(s==x&&e==y){lz+=nv;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo();r->ppo();
		v=max(l->v,r->v);
	}
};

struct tree{
	int s,e;
	node *root;
	vector<ii> ranges;
	tree(int _s,int _e){
		s=_s;e=_e;
		root=new node(s,e);
		ranges.resize(e-s+1);
	}
	void up(int x,int y,ll nv){
		root->up(x,y,nv);
	}
	ll qry(){
		root->ppo();
		ll ans=root->v.fi;
		int i=root->v.se;
		root->up(ranges[i].fi,ranges[i].se,-LINF);
		if(root->v.fi>=0)ans+=root->v.fi;
		up(ranges[i].fi,ranges[i].se,LINF);
		return ans;
	}
	
}*root[maxn];

int n,q,sub[maxn];ll w;
bool mark[maxn];
vii AL[maxn];
vector<edge> edges;

void find_sz(int u,int p){
	sub[u]=1;
	for(auto[v,i]:AL[u]){
		if(mark[v]||v==p)continue;
		find_sz(v,u);
		sub[u]+=sub[v];
	}
}

int cnt;
vii ranges;

ii dfs(int u,int p,int c){
	ii range={cnt,cnt};++cnt;
	for(auto[v,i]:AL[u]){
		if(mark[v]||v==p)continue;
		ii res=dfs(v,u,c);
		edges[i].comp.pb(c);
		edges[i].range.pb(res);
		mxto(range.se,res.se);
		if(p==-1)ranges.pb(res);
	}
	return range;
}

void decomp(int u){
	find_sz(u,-1);
	int c=u;
	int idk=0;
	while(true){
		++idk;
		bool val=true;
		for(auto[v,i]:AL[u]){
			if(!mark[v]&&sub[v]<sub[c]&&sub[v]>sub[u]/2){
				c=v;val=false;break;
			}
		}
		if(val)break;
		if(idk>n)exit(1);
	}
	
	cnt=0;
	ranges.clear();
	
	dfs(c,-1,c);
	
	root[c]=new tree(0,cnt-1);
	
	for(int i=0;i<sz(ranges);++i){
		for(int j=ranges[i].fi;j<=ranges[i].se;++j){
			root[c]->ranges[j]=ranges[i];
		}
	}
	
	mark[c]=true;
	for(auto[v,i]:AL[c]){
		if(!mark[v])decomp(v);
	}
}

int main(){
	sf("%d%d%lld",&n,&q,&w);
	for(int i=0;i<n-1;++i){
		int a,b;ll c;
		sf("%d%d%lld",&a,&b,&c);
		AL[a].pb({b,i});
		AL[b].pb({a,i});
		edges.pb({a,b,c,{},{}});
	}
	
	decomp(1);
	
	for(edge &e:edges){
		for(int i=0;i<sz(e.comp);++i){
			ii rng=e.range[i];
			root[e.comp[i]]->up(rng.fi,rng.se,e.w);
		}
	}
	
	set<li> s;
	for(int i=1;i<=n;++i){
		s.insert({root[i]->qry(),i});
	}
	
	ll ans=0;
	for(int i=0;i<q;++i){
		int idx;ll nw;
		sf("%d%lld",&idx,&nw);
		idx=(idx+ans)%(n-1);
		nw=(nw+ans)%w;
		edge &e=edges[idx];
		ll ow=e.w;
		e.w=nw;
		
		//dbg("upd: %d %lld\n",idx,nw);
		
		for(int i=0;i<sz(e.comp);++i){
			ii rng=e.range[i];
			int c=e.comp[i];
			
			ll old=root[c]->qry();
			root[c]->up(rng.fi,rng.se,nw-ow);
			ll upd=root[c]->qry();
			s.erase(s.find({old,c}));
			s.insert({upd,c});
		}
		
		ans=(*--s.end()).fi;
		
		pf("%lld\n",ans);
	}
}

Compilation message

diameter.cpp: In function 'int main()':
diameter.cpp:179:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |  sf("%d%d%lld",&n,&q,&w);
      |    ^
diameter.cpp:182:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  182 |   sf("%d%d%lld",&a,&b,&c);
      |     ^
diameter.cpp:205:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |   sf("%d%lld",&idx,&nw);
      |     ^

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2600 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 3 ms 2664 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2668 KB Output is correct
13 Correct 3 ms 2660 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2772 KB Output is correct
18 Correct 5 ms 2788 KB Output is correct

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2600 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 3 ms 2664 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2668 KB Output is correct
13 Correct 3 ms 2660 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2772 KB Output is correct
18 Correct 5 ms 2788 KB Output is correct
19 Correct 82 ms 4336 KB Output is correct
20 Correct 147 ms 5272 KB Output is correct
21 Correct 524 ms 9888 KB Output is correct
22 Correct 1529 ms 23076 KB Output is correct
23 Correct 157 ms 11728 KB Output is correct
24 Correct 1004 ms 37412 KB Output is correct
25 Correct 4398 ms 120360 KB Output is correct
26 Execution timed out 5093 ms 917208 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 18 ms 2808 KB Output is correct
5 Correct 81 ms 3576 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 5 ms 2928 KB Output is correct
10 Correct 29 ms 3184 KB Output is correct
11 Correct 137 ms 3872 KB Output is correct
12 Correct 8 ms 5324 KB Output is correct
13 Correct 8 ms 5324 KB Output is correct
14 Correct 12 ms 5388 KB Output is correct
15 Correct 47 ms 5580 KB Output is correct
16 Correct 193 ms 6268 KB Output is correct
17 Correct 138 ms 55488 KB Output is correct
18 Correct 137 ms 55484 KB Output is correct
19 Correct 142 ms 55716 KB Output is correct
20 Correct 191 ms 55696 KB Output is correct
21 Correct 431 ms 56308 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 4052 KB Output is correct
2 Correct 59 ms 4212 KB Output is correct
3 Correct 278 ms 4760 KB Output is correct
4 Correct 545 ms 5084 KB Output is correct
5 Correct 70 ms 22000 KB Output is correct
6 Correct 168 ms 22116 KB Output is correct
7 Correct 591 ms 22576 KB Output is correct
8 Correct 1153 ms 23160 KB Output is correct
9 Correct 391 ms 115376 KB Output is correct
10 Correct 544 ms 115584 KB Output is correct
11 Correct 1205 ms 115888 KB Output is correct
12 Correct 2021 ms 116252 KB Output is correct
13 Correct 845 ms 241144 KB Output is correct
14 Correct 1042 ms 241300 KB Output is correct
15 Correct 2001 ms 241532 KB Output is correct
16 Correct 3134 ms 241768 KB Output is correct
17 Correct 4594 ms 241932 KB Output is correct

Subtask #5
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2685 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2600 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2664 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Correct 2 ms 2668 KB Output is correct
10 Correct 3 ms 2664 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2668 KB Output is correct
13 Correct 3 ms 2660 KB Output is correct
14 Correct 2 ms 2660 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 2 ms 2772 KB Output is correct
17 Correct 3 ms 2772 KB Output is correct
18 Correct 5 ms 2788 KB Output is correct
19 Correct 82 ms 4336 KB Output is correct
20 Correct 147 ms 5272 KB Output is correct
21 Correct 524 ms 9888 KB Output is correct
22 Correct 1529 ms 23076 KB Output is correct
23 Correct 157 ms 11728 KB Output is correct
24 Correct 1004 ms 37412 KB Output is correct
25 Correct 4398 ms 120360 KB Output is correct
26 Execution timed out 5093 ms 917208 KB Time limit exceeded
27 Halted 0 ms 0 KB -