oj.uz

Submission #570559

# Submission time Handle Problem Language Result Execution time Memory
570559 2022-05-30T13:05:38 Z kwongweng Meetings 2 (JOI21_meetings2) C++17
20 / 100
 4000 ms 16184 KB 
#include <bits/stdc++.h>
using namespace std;

/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
*/
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
 
ll MOD = 1000000007;
ll MOD1 = 998244353;
 
ll power(ll base, ll n){
	if (n == 0) return 1;
	if (n == 1) return base;
	ll halfn = power(base, n/2);
	if (n % 2 == 0) return (halfn * halfn) % MOD;
	return (((halfn * halfn) % MOD) * base) % MOD;
}
 
ll inverse(ll n){
	return power(n, MOD-2);
}
 
ll add(ll a, ll b){
	return (a+b) % MOD;
}
 
ll mul(ll a, ll b){
	a %= MOD;
	return (a*b) % MOD;
}
 
ll gcd(ll a, ll b){
    if (a == 1) return 1;
    if (a == 0) return b;
    return gcd(b%a, a);
}

ld pi = 3.141592653589793238;
struct segtree{
	vector<ll> op, ans;
	int sz = 0;
	void init(int n){
		sz = n;
		op.assign(4*n, -1);
		ans.assign(4*n, 0);
	}
	void prop(int v, int tl, int tr){
		if (op[v] == -1 || tl == tr) return;
		int tm = (tl+tr)/2;
		op[2*v] = op[v];
		op[2*v+1] = op[v];
		ll len1 = tm-tl+1, len2 = tr-tm;
		ans[2*v] = op[v] * len1;
		ans[2*v+1] = op[v] * len2;
		op[v] = -1;
	}
	void update(int v, int tl, int tr, int l, int r, int val){
		prop(v, tl, tr);
		if (l > r) return;
		if (tl == l && tr == r){
			op[v] = val;
			ll len = tr-tl+1;
			ans[v] = val * len;
			return;
		}
		int tm = (tl+tr)/2;
		update(2*v, tl, tm, l, min(r,tm), val);
		update(2*v+1, tm+1, tr, max(l, tm+1), r, val);
		ans[v] = ans[2*v] + ans[2*v+1];
	}
	void update(int l, int r, int val){
		update(1, 0, sz-1, l, r, val);
	}
	ll get(int v, int tl, int tr, int l, int r){
		prop(v, tl, tr);
		if (l > r) return 0;
		if (tl == l && tr == r) return ans[v];
		int tm = (tl+tr)/2;
		ll m1 = get(2*v, tl, tm, l, min(r, tm));
		ll m2 = get(2*v+1, tm+1, tr, max(l, tm+1), r);
		return m1 + m2;
	}
	ll get(int l, int r){
		return get(1, 0, sz-1, l, r);
	}
};

const int N = 200001;
vi g[N], sz(N), ans(N,1), dist(N);

void dfs1(int u, int p){
	sz[u] = 1;
	for (int v : g[u]){
		if (v==p) continue;
		dist[v] = dist[u]+1;
		dfs1(v,u);
		sz[u]+=sz[v];
	}
}

void dfs2(int u, int p, int cur){
	int val = min(cur, sz[u]);
	ans[val*2] = max(ans[val*2], dist[u]+1);
	for (int v : g[u]){
		if (v==p) continue;
		dfs2(v,u,cur);
	}
}

void solve(){
    int n; cin >> n;
	FOR(i,0,n-1){
		int u, v; cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	FOR(i,1,n+1){
		dfs1(i,0);
		for (int u : g[i]){
			dfs2(u,i,n-sz[u]);
		}
		FOR(j,1,n+1) dist[j] = 0;
	}
	ROF(i,n/2,1){
		ans[i*2] = max(ans[i*2], ans[(i+1)*2]);
	}
	FOR(i,1,n+1){
		if (i % 2 == 1) cout << 1 << '\n';
		else cout << ans[i] << '\n';
	}
}

int main(){
    cout << fixed << setprecision(8);
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	}
    int TC = 1;
    //cin >> TC;
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message

meetings2.cpp: In function 'int main()':
meetings2.cpp:152:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
meetings2.cpp:153:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |   freopen("output.txt", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7376 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7376 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 558 ms 7544 KB Output is correct
23 Correct 558 ms 7548 KB Output is correct
24 Correct 551 ms 7552 KB Output is correct
25 Correct 585 ms 7548 KB Output is correct
26 Correct 537 ms 7536 KB Output is correct
27 Correct 552 ms 7628 KB Output is correct
28 Correct 595 ms 7552 KB Output is correct
29 Correct 553 ms 7628 KB Output is correct
30 Correct 558 ms 7536 KB Output is correct
31 Correct 573 ms 7652 KB Output is correct
32 Correct 545 ms 7636 KB Output is correct
33 Correct 452 ms 7784 KB Output is correct
34 Correct 490 ms 7632 KB Output is correct
35 Correct 340 ms 7556 KB Output is correct
36 Correct 387 ms 7560 KB Output is correct
37 Correct 344 ms 7548 KB Output is correct
38 Correct 385 ms 7684 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 5 ms 7376 KB Output is correct
7 Correct 4 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 4 ms 7380 KB Output is correct
11 Correct 4 ms 7380 KB Output is correct
12 Correct 4 ms 7380 KB Output is correct
13 Correct 4 ms 7380 KB Output is correct
14 Correct 4 ms 7380 KB Output is correct
15 Correct 5 ms 7508 KB Output is correct
16 Correct 4 ms 7380 KB Output is correct
17 Correct 4 ms 7380 KB Output is correct
18 Correct 5 ms 7380 KB Output is correct
19 Correct 4 ms 7380 KB Output is correct
20 Correct 4 ms 7380 KB Output is correct
21 Correct 4 ms 7380 KB Output is correct
22 Correct 558 ms 7544 KB Output is correct
23 Correct 558 ms 7548 KB Output is correct
24 Correct 551 ms 7552 KB Output is correct
25 Correct 585 ms 7548 KB Output is correct
26 Correct 537 ms 7536 KB Output is correct
27 Correct 552 ms 7628 KB Output is correct
28 Correct 595 ms 7552 KB Output is correct
29 Correct 553 ms 7628 KB Output is correct
30 Correct 558 ms 7536 KB Output is correct
31 Correct 573 ms 7652 KB Output is correct
32 Correct 545 ms 7636 KB Output is correct
33 Correct 452 ms 7784 KB Output is correct
34 Correct 490 ms 7632 KB Output is correct
35 Correct 340 ms 7556 KB Output is correct
36 Correct 387 ms 7560 KB Output is correct
37 Correct 344 ms 7548 KB Output is correct
38 Correct 385 ms 7684 KB Output is correct
39 Execution timed out 4053 ms 16184 KB Time limit exceeded
40 Halted 0 ms 0 KB -