oj.uz

Submission #1078555

# Submission time Handle Problem Language Result Execution time Memory
1078555 2024-08-27T20:46:58 Z vjudge1 Unique Cities (JOI19_ho_t5) C++17
32 / 100
 187 ms 39536 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define plx pair<ll,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
using namespace std;
const int mxn=2e5+5,inf=998244353;
vector<int>g[mxn];
int c[mxn];
int ans[mxn]{0};
stack<int>st;
int cc[mxn]{0},cur=0;
int d[mxn]{0};
void add(int x){
    if(++cc[c[d[x]]]==1)cur++;
    st.push(x);
}
void del(int x){
    while(!st.empty()&&st.top()>=x){
        if(--cc[c[d[st.top()]]]==0)cur--;
        st.pop();
    }
}
pii mx[mxn][2];
int tmp=0,mem=0,rt;
void precal(int u,int p){
    if(mem<d[u])mem=d[u],tmp=u;
    mx[u][0]=mx[u][1]={0,0};
    for(auto v:g[u]){
        if(v==p)continue;
        d[v]=d[u]+1;precal(v,u);
        pii mxe = {mx[v][0].f+1,v};
        if(mxe>mx[u][0])swap(mxe,mx[u][0]);
        if(mxe>mx[u][1])swap(mxe,mx[u][1]);
    }
}
void cal(int u,int p,int de){
    d[de]=u;
    if(mx[u][0].s){
        if(mx[u][1].s)del(de-mx[u][1].f);
        add(de);
        cal(mx[u][0].s,u,de+1);
        del(de-mx[u][0].f);
    }if(!st.empty()&&st.top()==de)del(de);
    ans[u]=max(ans[u],cur);
    for(auto v:g[u]){
        if(v==p||v==mx[u][0].s)continue;
        if(st.empty()||st.top()!=de)add(de);
        cal(v,u,de+1);
    }
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n-1;i++){
        int u,v;cin>>u>>v;g[u].pb(v);g[v].pb(u);
    }for(int i=1;i<=n;i++)cin>>c[i];
    precal(1,1);rt=tmp;mem=tmp=0;
    memset(d,0,sizeof d);precal(rt,rt);
    cal(rt,rt,0);rt=tmp;memset(d,0,sizeof d);
    while(!st.empty())st.pop();cur=0;precal(rt,rt);cal(rt,rt,0);
    for(int i=1;i<=n;i++)cout<<ans[i]<<'\n';
}

Compilation message

joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:68:5: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   68 |     while(!st.empty())st.pop();cur=0;precal(rt,rt);cal(rt,rt,0);
      |     ^~~~~
joi2019_ho_t5.cpp:68:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   68 |     while(!st.empty())st.pop();cur=0;precal(rt,rt);cal(rt,rt,0);
      |                                ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Incorrect 3 ms 5980 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 13936 KB Output is correct
2 Correct 89 ms 25088 KB Output is correct
3 Correct 18 ms 9308 KB Output is correct
4 Correct 131 ms 20304 KB Output is correct
5 Correct 181 ms 39536 KB Output is correct
6 Correct 187 ms 29572 KB Output is correct
7 Correct 117 ms 20176 KB Output is correct
8 Correct 141 ms 22096 KB Output is correct
9 Correct 153 ms 21512 KB Output is correct
10 Correct 125 ms 21512 KB Output is correct
11 Correct 71 ms 20932 KB Output is correct
12 Correct 166 ms 32080 KB Output is correct
13 Correct 144 ms 29656 KB Output is correct
14 Correct 153 ms 29104 KB Output is correct
15 Correct 66 ms 20676 KB Output is correct
16 Correct 128 ms 33356 KB Output is correct
17 Correct 136 ms 29900 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 18936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Incorrect 3 ms 5980 KB Output isn't correct
3 Halted 0 ms 0 KB -