oj.uz

Submission #836361

# Submission time Handle Problem Language Result Execution time Memory
836361 2023-08-24T10:33:51 Z sunwukong123 Meetings 2 (JOI21_meetings2) C++14
20 / 100
 4000 ms 124620 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 200005;
const int inf=1000000500ll;
const int oo =1000000000000000000ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
vector<pi> adj[MAXN];
/*
this is essentially finding diameter while updating some edges from weight 1 to weight 0
when should you update an edge from weight 1 to weight 0?
at t=min(sz[a],sz[b])
so just use the dynamicdiameter code to solve this as well
note that you can probably simplify many things, because we are always removing the leaf, and the edges are unweighted.
*/
int sz[MAXN];
vector<int> T[MAXN];
int id[MAXN];
int TIME;
int in[MAXN];
int out[MAXN];
struct node {
	int s,e,m;
	int a,b,c,ab,bc,abc;
	int lazy;
	node *l, *r;
	node(int _s, int _e){
		s=_s;e=_e;m=(s+e)/2;
		a=b=c=ab=bc=abc=lazy=0;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void value(){
		if(lazy==0)return;
		a+=lazy;
		b-=2*lazy;
		c+=lazy;
		ab-=lazy;
		bc-=lazy;
		if(s!=e){
			l->lazy+=lazy;
			r->lazy+=lazy;
		}
		lazy=0;
	}
	void update(int x, int y, int nval){
		value();
		if(s==e){
			lazy+=nval;
			return;
		}
		if(x>m)r->update(x,y,nval);
		else if(y<=m)l->update(x,y,nval);
		else {
			l->update(x,m,nval);
			r->update(m+1,y,nval);
		}

		l->value();r->value();
		a=max(l->a,r->a);
		b=max(l->b,r->b);
		c=max(l->c,r->c);
		ab=max({l->ab,r->ab,l->a+r->b});
		bc=max({l->bc,r->bc,l->b+r->c});
		abc=max({l->abc,r->abc,l->a+r->bc,l->ab+r->c});
		
	}
}*seg=new node(0,2*MAXN);
void dfs(int x, int p){
	in[x]=TIME++;
	sz[x]=1;
	for(auto v:adj[x])if(v.first!=p){
		dfs(v.first,x);
		sz[x]+=sz[v.first];
		id[v.second]=v.first;
		out[x]=TIME++;
	}
	if(out[x]==0)out[x]=in[x];

	int ti=min(sz[x],n-sz[x]);
	T[ti].push_back(x);
}
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1;i<=n-1;i++){
		int a,b; cin >> a >> b;
		adj[a].push_back({b,i});
		adj[b].push_back({a,i});
	}
	dfs(1,-1);
	for(int i=1;i<=n-1;i++){
		seg->update(in[id[i]],out[id[i]],1);
	}
	for(int i=1;i<=n/2;i++){
		cout<<"1\n";
		cout<<1+seg->abc<<'\n';
		for(auto x:T[i]){

			seg->update(in[x],out[x],-1);
		}
	}
	if(n%2==1)cout<<"1\n";
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 97400 KB Output is correct
2 Correct 49 ms 97356 KB Output is correct
3 Correct 48 ms 97356 KB Output is correct
4 Correct 49 ms 97356 KB Output is correct
5 Correct 50 ms 97356 KB Output is correct
6 Correct 49 ms 97392 KB Output is correct
7 Correct 49 ms 97316 KB Output is correct
8 Correct 48 ms 97356 KB Output is correct
9 Correct 55 ms 97356 KB Output is correct
10 Correct 49 ms 97356 KB Output is correct
11 Correct 49 ms 97356 KB Output is correct
12 Correct 49 ms 97408 KB Output is correct
13 Correct 49 ms 97328 KB Output is correct
14 Correct 50 ms 97324 KB Output is correct
15 Correct 49 ms 97356 KB Output is correct
16 Correct 49 ms 97476 KB Output is correct
17 Correct 50 ms 97356 KB Output is correct
18 Correct 51 ms 97356 KB Output is correct
19 Correct 50 ms 97356 KB Output is correct
20 Correct 60 ms 97288 KB Output is correct
21 Correct 48 ms 97356 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 97400 KB Output is correct
2 Correct 49 ms 97356 KB Output is correct
3 Correct 48 ms 97356 KB Output is correct
4 Correct 49 ms 97356 KB Output is correct
5 Correct 50 ms 97356 KB Output is correct
6 Correct 49 ms 97392 KB Output is correct
7 Correct 49 ms 97316 KB Output is correct
8 Correct 48 ms 97356 KB Output is correct
9 Correct 55 ms 97356 KB Output is correct
10 Correct 49 ms 97356 KB Output is correct
11 Correct 49 ms 97356 KB Output is correct
12 Correct 49 ms 97408 KB Output is correct
13 Correct 49 ms 97328 KB Output is correct
14 Correct 50 ms 97324 KB Output is correct
15 Correct 49 ms 97356 KB Output is correct
16 Correct 49 ms 97476 KB Output is correct
17 Correct 50 ms 97356 KB Output is correct
18 Correct 51 ms 97356 KB Output is correct
19 Correct 50 ms 97356 KB Output is correct
20 Correct 60 ms 97288 KB Output is correct
21 Correct 48 ms 97356 KB Output is correct
22 Correct 54 ms 97824 KB Output is correct
23 Correct 53 ms 97740 KB Output is correct
24 Correct 54 ms 97820 KB Output is correct
25 Correct 54 ms 97776 KB Output is correct
26 Correct 55 ms 97740 KB Output is correct
27 Correct 54 ms 97740 KB Output is correct
28 Correct 63 ms 97836 KB Output is correct
29 Correct 55 ms 97740 KB Output is correct
30 Correct 55 ms 97740 KB Output is correct
31 Correct 55 ms 97736 KB Output is correct
32 Correct 180 ms 98124 KB Output is correct
33 Correct 274 ms 98016 KB Output is correct
34 Correct 55 ms 97724 KB Output is correct
35 Correct 53 ms 97796 KB Output is correct
36 Correct 75 ms 97740 KB Output is correct
37 Correct 53 ms 97740 KB Output is correct
38 Correct 118 ms 98024 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 97400 KB Output is correct
2 Correct 49 ms 97356 KB Output is correct
3 Correct 48 ms 97356 KB Output is correct
4 Correct 49 ms 97356 KB Output is correct
5 Correct 50 ms 97356 KB Output is correct
6 Correct 49 ms 97392 KB Output is correct
7 Correct 49 ms 97316 KB Output is correct
8 Correct 48 ms 97356 KB Output is correct
9 Correct 55 ms 97356 KB Output is correct
10 Correct 49 ms 97356 KB Output is correct
11 Correct 49 ms 97356 KB Output is correct
12 Correct 49 ms 97408 KB Output is correct
13 Correct 49 ms 97328 KB Output is correct
14 Correct 50 ms 97324 KB Output is correct
15 Correct 49 ms 97356 KB Output is correct
16 Correct 49 ms 97476 KB Output is correct
17 Correct 50 ms 97356 KB Output is correct
18 Correct 51 ms 97356 KB Output is correct
19 Correct 50 ms 97356 KB Output is correct
20 Correct 60 ms 97288 KB Output is correct
21 Correct 48 ms 97356 KB Output is correct
22 Correct 54 ms 97824 KB Output is correct
23 Correct 53 ms 97740 KB Output is correct
24 Correct 54 ms 97820 KB Output is correct
25 Correct 54 ms 97776 KB Output is correct
26 Correct 55 ms 97740 KB Output is correct
27 Correct 54 ms 97740 KB Output is correct
28 Correct 63 ms 97836 KB Output is correct
29 Correct 55 ms 97740 KB Output is correct
30 Correct 55 ms 97740 KB Output is correct
31 Correct 55 ms 97736 KB Output is correct
32 Correct 180 ms 98124 KB Output is correct
33 Correct 274 ms 98016 KB Output is correct
34 Correct 55 ms 97724 KB Output is correct
35 Correct 53 ms 97796 KB Output is correct
36 Correct 75 ms 97740 KB Output is correct
37 Correct 53 ms 97740 KB Output is correct
38 Correct 118 ms 98024 KB Output is correct
39 Correct 881 ms 118592 KB Output is correct
40 Correct 789 ms 117696 KB Output is correct
41 Correct 856 ms 118636 KB Output is correct
42 Correct 988 ms 118860 KB Output is correct
43 Correct 874 ms 118904 KB Output is correct
44 Correct 964 ms 118904 KB Output is correct
45 Execution timed out 4054 ms 124620 KB Time limit exceeded
46 Halted 0 ms 0 KB -