oj.uz

Submission #540674

# Submission time Handle Problem Language Result Execution time Memory
540674 2022-03-21T11:01:50 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;ll ans;
	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();
		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;
	while(q--){
		ll idx,nw;
		sf("%lld%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]->ans;
			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("%lld%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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 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 2704 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 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 3 ms 2772 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 3 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 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 2704 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 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 3 ms 2772 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 3 ms 2900 KB Output is correct
19 Correct 57 ms 4300 KB Output is correct
20 Correct 92 ms 5260 KB Output is correct
21 Correct 395 ms 9964 KB Output is correct
22 Correct 1133 ms 22820 KB Output is correct
23 Correct 110 ms 11628 KB Output is correct
24 Correct 701 ms 37372 KB Output is correct
25 Correct 3325 ms 120192 KB Output is correct
26 Execution timed out 5129 ms 917284 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 15 ms 2800 KB Output is correct
5 Correct 65 ms 3364 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 4 ms 2900 KB Output is correct
10 Correct 25 ms 3144 KB Output is correct
11 Correct 113 ms 3628 KB Output is correct
12 Correct 8 ms 5324 KB Output is correct
13 Correct 9 ms 5324 KB Output is correct
14 Correct 11 ms 5452 KB Output is correct
15 Correct 37 ms 5532 KB Output is correct
16 Correct 174 ms 6176 KB Output is correct
17 Correct 146 ms 56612 KB Output is correct
18 Correct 145 ms 56708 KB Output is correct
19 Correct 149 ms 56740 KB Output is correct
20 Correct 186 ms 56848 KB Output is correct
21 Correct 360 ms 57496 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4052 KB Output is correct
2 Correct 45 ms 4212 KB Output is correct
3 Correct 201 ms 4560 KB Output is correct
4 Correct 384 ms 4940 KB Output is correct
5 Correct 70 ms 22028 KB Output is correct
6 Correct 151 ms 22184 KB Output is correct
7 Correct 467 ms 22492 KB Output is correct
8 Correct 889 ms 23040 KB Output is correct
9 Correct 385 ms 115808 KB Output is correct
10 Correct 514 ms 115928 KB Output is correct
11 Correct 1072 ms 116504 KB Output is correct
12 Correct 1735 ms 116764 KB Output is correct
13 Correct 829 ms 242344 KB Output is correct
14 Correct 991 ms 242332 KB Output is correct
15 Correct 1643 ms 242820 KB Output is correct
16 Correct 2402 ms 242832 KB Output is correct
17 Correct 3694 ms 242976 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2739 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 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 1 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 2704 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 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 3 ms 2772 KB Output is correct
17 Correct 2 ms 2772 KB Output is correct
18 Correct 3 ms 2900 KB Output is correct
19 Correct 57 ms 4300 KB Output is correct
20 Correct 92 ms 5260 KB Output is correct
21 Correct 395 ms 9964 KB Output is correct
22 Correct 1133 ms 22820 KB Output is correct
23 Correct 110 ms 11628 KB Output is correct
24 Correct 701 ms 37372 KB Output is correct
25 Correct 3325 ms 120192 KB Output is correct
26 Execution timed out 5129 ms 917284 KB Time limit exceeded
27 Halted 0 ms 0 KB -