oj.uz

Submission #1078556

# Submission time Handle Problem Language Result Execution time Memory
1078556 2024-08-27T20:48:50 Z vjudge1 Unique Cities (JOI19_ho_t5) C++17
32 / 100
 176 ms 40140 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();memset(cc,0,sizeof cc);
    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();memset(cc,0,sizeof cc);
      |     ^~~~~
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();memset(cc,0,sizeof cc);
      |                                ^~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Incorrect 4 ms 6748 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 62 ms 14696 KB Output is correct
2 Correct 77 ms 25940 KB Output is correct
3 Correct 19 ms 10076 KB Output is correct
4 Correct 127 ms 21072 KB Output is correct
5 Correct 157 ms 40140 KB Output is correct
6 Correct 174 ms 30376 KB Output is correct
7 Correct 122 ms 20944 KB Output is correct
8 Correct 123 ms 22432 KB Output is correct
9 Correct 144 ms 21820 KB Output is correct
10 Correct 137 ms 21840 KB Output is correct
11 Correct 77 ms 21212 KB Output is correct
12 Correct 154 ms 32428 KB Output is correct
13 Correct 137 ms 30148 KB Output is correct
14 Correct 139 ms 29392 KB Output is correct
15 Correct 69 ms 21184 KB Output is correct
16 Correct 176 ms 33872 KB Output is correct
17 Correct 150 ms 30416 KB Output is correct

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

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