oj.uz

Submission #1078554

# Submission time Handle Problem Language Result Execution time Memory
1078554 2024-08-27T20:43:36 Z vjudge1 Unique Cities (JOI19_ho_t5) C++17
32 / 100
 176 ms 39532 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)st.pop();
    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 3 ms 5724 KB Output is correct
2 Incorrect 4 ms 6076 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 66 ms 13932 KB Output is correct
2 Correct 81 ms 25168 KB Output is correct
3 Correct 18 ms 9052 KB Output is correct
4 Correct 122 ms 20184 KB Output is correct
5 Correct 165 ms 39532 KB Output is correct
6 Correct 147 ms 29784 KB Output is correct
7 Correct 113 ms 20172 KB Output is correct
8 Correct 143 ms 22100 KB Output is correct
9 Correct 132 ms 21588 KB Output is correct
10 Correct 139 ms 21328 KB Output is correct
11 Correct 73 ms 20904 KB Output is correct
12 Correct 176 ms 32080 KB Output is correct
13 Correct 133 ms 29644 KB Output is correct
14 Correct 131 ms 29132 KB Output is correct
15 Correct 67 ms 20900 KB Output is correct
16 Correct 130 ms 33580 KB Output is correct
17 Correct 137 ms 29744 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 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 5724 KB Output is correct
2 Incorrect 4 ms 6076 KB Output isn't correct
3 Halted 0 ms 0 KB -