oj.uz

Submission #540648

# Submission time Handle Problem Language Result Execution time Memory
540648 2022-03-21T10:29:08 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;
	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){
		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:176:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  176 |  sf("%d%d%lld",&n,&q,&w);
      |    ^
diameter.cpp:179:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |   sf("%d%d%lld",&a,&b,&c);
      |     ^
diameter.cpp:202:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  202 |   sf("%d%lld",&idx,&nw);
      |     ^

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 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 2660 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 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 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 4 ms 2900 KB Output is correct
19 Correct 74 ms 4344 KB Output is correct
20 Correct 140 ms 5284 KB Output is correct
21 Correct 478 ms 9960 KB Output is correct
22 Correct 1321 ms 22696 KB Output is correct
23 Correct 143 ms 11716 KB Output is correct
24 Correct 928 ms 37592 KB Output is correct
25 Correct 3918 ms 120260 KB Output is correct
26 Execution timed out 5124 ms 917472 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 2644 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 20 ms 2940 KB Output is correct
5 Correct 88 ms 3308 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 2900 KB Output is correct
10 Correct 31 ms 3092 KB Output is correct
11 Correct 138 ms 3640 KB Output is correct
12 Correct 11 ms 5324 KB Output is correct
13 Correct 8 ms 5324 KB Output is correct
14 Correct 12 ms 5324 KB Output is correct
15 Correct 46 ms 5480 KB Output is correct
16 Correct 197 ms 6136 KB Output is correct
17 Correct 132 ms 55184 KB Output is correct
18 Correct 139 ms 55196 KB Output is correct
19 Correct 136 ms 55076 KB Output is correct
20 Correct 198 ms 55296 KB Output is correct
21 Correct 431 ms 55740 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4052 KB Output is correct
2 Correct 59 ms 4240 KB Output is correct
3 Correct 270 ms 4624 KB Output is correct
4 Correct 555 ms 4836 KB Output is correct
5 Correct 72 ms 21872 KB Output is correct
6 Correct 180 ms 22032 KB Output is correct
7 Correct 591 ms 22336 KB Output is correct
8 Correct 1198 ms 22824 KB Output is correct
9 Correct 403 ms 114996 KB Output is correct
10 Correct 556 ms 114996 KB Output is correct
11 Correct 1201 ms 115392 KB Output is correct
12 Correct 2011 ms 115908 KB Output is correct
13 Correct 832 ms 240676 KB Output is correct
14 Correct 1012 ms 240788 KB Output is correct
15 Correct 1813 ms 241172 KB Output is correct
16 Correct 2771 ms 241336 KB Output is correct
17 Correct 4272 ms 241272 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2673 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 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 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 2660 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 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 3 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 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 4 ms 2900 KB Output is correct
19 Correct 74 ms 4344 KB Output is correct
20 Correct 140 ms 5284 KB Output is correct
21 Correct 478 ms 9960 KB Output is correct
22 Correct 1321 ms 22696 KB Output is correct
23 Correct 143 ms 11716 KB Output is correct
24 Correct 928 ms 37592 KB Output is correct
25 Correct 3918 ms 120260 KB Output is correct
26 Execution timed out 5124 ms 917472 KB Time limit exceeded
27 Halted 0 ms 0 KB -