oj.uz

Submission #540645

# Submission time Handle Problem Language Result Execution time Memory
540645 2022-03-21T10:20:35 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<int> block;
	vector<ii> ranges;
	tree(int _s,int _e){
		s=_s;e=_e;
		root=new node(s,e);
		block.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=block[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;
	while(true){
		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;
	}
	
	cnt=0;
	ranges.clear();
	
	dfs(c,-1,c);
	
	root[c]=new tree(0,cnt-1);
	
	for(int i=0;i<sz(ranges);++i){
		root[c]->ranges.pb(ranges[i]);
		for(int j=ranges[i].fi;j<=ranges[i].se;++j){
			root[c]->block[j]=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){
		if(root[i]->s==root[i]->e)continue;
		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:178:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |  sf("%d%d%lld",&n,&q,&w);
      |    ^
diameter.cpp:181:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  181 |   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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 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 2644 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 3 ms 2772 KB Output is correct
17 Correct 3 ms 2792 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 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 2644 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 3 ms 2772 KB Output is correct
17 Correct 3 ms 2792 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 79 ms 4308 KB Output is correct
20 Correct 142 ms 5244 KB Output is correct
21 Correct 548 ms 9960 KB Output is correct
22 Correct 1318 ms 22228 KB Output is correct
23 Correct 147 ms 11592 KB Output is correct
24 Correct 879 ms 36720 KB Output is correct
25 Correct 3830 ms 117336 KB Output is correct
26 Execution timed out 5091 ms 893636 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2660 KB Output is correct
3 Correct 4 ms 2644 KB Output is correct
4 Correct 17 ms 2872 KB Output is correct
5 Correct 79 ms 3236 KB Output is correct
6 Correct 2 ms 2660 KB Output is correct
7 Correct 3 ms 2920 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 5 ms 2932 KB Output is correct
10 Correct 28 ms 3064 KB Output is correct
11 Correct 136 ms 3772 KB Output is correct
12 Correct 7 ms 5196 KB Output is correct
13 Correct 8 ms 5100 KB Output is correct
14 Correct 11 ms 5136 KB Output is correct
15 Correct 41 ms 5324 KB Output is correct
16 Correct 179 ms 5828 KB Output is correct
17 Correct 114 ms 52488 KB Output is correct
18 Correct 110 ms 52408 KB Output is correct
19 Correct 116 ms 52284 KB Output is correct
20 Correct 166 ms 52388 KB Output is correct
21 Correct 367 ms 52892 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4052 KB Output is correct
2 Correct 59 ms 4216 KB Output is correct
3 Correct 274 ms 4468 KB Output is correct
4 Correct 531 ms 4764 KB Output is correct
5 Correct 69 ms 21696 KB Output is correct
6 Correct 170 ms 21820 KB Output is correct
7 Correct 567 ms 22068 KB Output is correct
8 Correct 1089 ms 22556 KB Output is correct
9 Correct 379 ms 113508 KB Output is correct
10 Correct 526 ms 113508 KB Output is correct
11 Correct 1144 ms 113832 KB Output is correct
12 Correct 1951 ms 114136 KB Output is correct
13 Correct 808 ms 237104 KB Output is correct
14 Correct 986 ms 237092 KB Output is correct
15 Correct 1751 ms 237360 KB Output is correct
16 Correct 2716 ms 237744 KB Output is correct
17 Correct 4209 ms 237568 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2764 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 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 2644 KB Output is correct
10 Correct 2 ms 2668 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 3 ms 2644 KB Output is correct
13 Correct 2 ms 2668 KB Output is correct
14 Correct 3 ms 2644 KB Output is correct
15 Correct 3 ms 2772 KB Output is correct
16 Correct 3 ms 2772 KB Output is correct
17 Correct 3 ms 2792 KB Output is correct
18 Correct 4 ms 2900 KB Output is correct
19 Correct 79 ms 4308 KB Output is correct
20 Correct 142 ms 5244 KB Output is correct
21 Correct 548 ms 9960 KB Output is correct
22 Correct 1318 ms 22228 KB Output is correct
23 Correct 147 ms 11592 KB Output is correct
24 Correct 879 ms 36720 KB Output is correct
25 Correct 3830 ms 117336 KB Output is correct
26 Execution timed out 5091 ms 893636 KB Time limit exceeded
27 Halted 0 ms 0 KB -