| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 804195 | 2023-08-03T07:31:00 Z | vjudge1 | Meetings 2 (JOI21_meetings2) | C++17 | 18 ms | 35608 KB |
#include <bits/stdc++.h>
using namespace std;
#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"
const int N = 5e5 + 9 , mod = 1e9 + 7;
ll d[N] = {} , a[N] = {}, dp[N] = {}, b[N] , c[N] , us[N] = {} , us1[N] = {} , p[N][20] , sz[N] = {} , root , timer = 0;
vector<int>v[N] ;
set<ll>st[N];
bool is_upper(int x , int y){
return (us[x] <= us[y] && us1[x] >= us1[y]);
}
ll lca(int x , int y){
if(is_upper(x , y))
return x;
if(is_upper(y , x))
return y;
for(int i = 19; i >= 0; i--)
if(p[x][i] && !is_upper(p[x][i] , y))
x = p[x][i] ;
return p[x][0];
}
ll dist(int x , int y){
return (d[x] + d[y] - 2 * (d[lca(x ,y)]));
}
void dfs(int n ){
us[n] = ++timer;
for(int i = 1; i < 20; i++)
p[n][i] = p[p[n][i - 1]][p[n][i - 1]];
for(auto to : v[n])
if(!us[to])
d[to] = d[n] + 1, p[to][0] = n , dfs(to);
sz[p[n][0]] += sz[n];
us1[n] = ++timer;
}
void solve(){
ll q , i , j , m ,n, z ,s = 0 , f , l , r , k , x , y , mn = 1e18 , mx = 0;
cin>>n;
for(i = 1; i < n; i++){
cin>>l>>r;
v[l].pb(r);
v[r].pb(l);
st[l].insert(r);
st[r].insert(l);
}
for(i = 1; i <= n; i++)
if(v[i].size() == 1)
root = i;
dfs(root);
set<pair<int,int>> s1 , s2;
for(i = 1; i <= n; i++){
b[i] = 1;
//cout<<st[i].size()<<" ";
if(st[i].size() == 1)
s1.insert({b[i] , i});
}
while(s1.size()){
auto it = s1.begin();
s2.insert({it->fi , it->se});
//cout<<it->fi<<" "<<it->se<<"\n";
if(st[it->se].size()){
x = *st[it->se].begin();
st[x].erase(it->se);
st[it->se].erase(x);
b[x] += b[it->se];
s2.insert({b[x] , x});
if(st[x].size() == 1)
s1.insert({b[x] , x});
}
s1.erase(it);
}
for(i = n; i >= 1; i--){
if(i % 2 == 1){
c[i] = 1;
}else {
mx = 2;
vector<int>v;
while(s2.size() && s2.rbegin()->fi >= i / 2)
v.pb(s2.rbegin()->se) , s2.erase({s2.rbegin()->fi , s2.rbegin()->se});
for(x= 0;x < v.size();x++)
for(y = x + 1; y < v.size(); y++)
mx = max(mx , dist(v[x] , v[y]) + 1);
c[i] = max(c[i] , mx);
}
}
for(i = 1; i <= n; i++)
cout<<c[i]<<"\n";
}
int main(){
TL;
/*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
*/
int t = 1;
//cin>>t;
while(t--)
{
solve();
}
}
// Author : حسن
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 35540 KB | Output is correct |
| 2 | Correct | 18 ms | 35608 KB | Output is correct |
| 3 | Correct | 17 ms | 35540 KB | Output is correct |
| 4 | Incorrect | 17 ms | 35496 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 35540 KB | Output is correct |
| 2 | Correct | 18 ms | 35608 KB | Output is correct |
| 3 | Correct | 17 ms | 35540 KB | Output is correct |
| 4 | Incorrect | 17 ms | 35496 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 18 ms | 35540 KB | Output is correct |
| 2 | Correct | 18 ms | 35608 KB | Output is correct |
| 3 | Correct | 17 ms | 35540 KB | Output is correct |
| 4 | Incorrect | 17 ms | 35496 KB | Output isn't correct |
| 5 | Halted | 0 ms | 0 KB | - |