oj.uz

Submission #250462

# Submission time Handle Problem Language Result Execution time Memory
250462 2020-07-18T04:41:07 Z combi1k1 Unique Cities (JOI19_ho_t5) C++14
0 / 100
 257 ms 17684 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll  long long
#define pb  push_back
#define X   first
#define Y   second
 
#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)
 
const int   N   = 2e5 + 1;
 
vector<int> g[N];
 
namespace Diameter  {
    int Max;
    int fin;
    int L, R;
 
    int dfs(int u,int p,int d)  {
        if (Max < d)    {
            Max = d;
            fin = u;
        }
        for(int v : g[u])   if (v != p)
            dfs(v,u,d + 1);
        return  fin;
    }
    int LamViecCanLam() {
        Max = fin = 0;  L = dfs(1,0,0);
        Max = fin = 0;  R = dfs(L,0,0);
 
        return  1;
    }
};
 
using Diameter::L;
using Diameter::R;
 
array<int,2> MaxDep[N];
 
int dep[N], dig[N];
int ans[N], cnt[N];
 
int res = 0;
 
int c[N];
 
stack<int>  st;
 
void add(int u) {
    st.push(u);
    cnt[c[u]]++;
 
    res += (cnt[c[u]] == 1);
}
void rem(int h) {
    while (st.size() && h <= dep[st.top()]) {
        int x = st.top();   st.pop();
        cnt[c[x]]--;
        res -= (cnt[c[x]] == 0);
    }
}
 
void upd(int u,int V)   {
    if (MaxDep[u][1] < V)   MaxDep[u][1] = V;
    if (MaxDep[u][1] > MaxDep[u][0])
        swap(MaxDep[u][1],MaxDep[u][0]);
}
 
void dfs(int u,int p)   {
    rem(2 * dep[u] - MaxDep[u][1]);
    add(u);
 
    for(int v : g[u])   if (v == dig[u])
        dfs(v,u);
 
    rem(2 * dep[u] - MaxDep[u][0]);
 
    ans[u] = max(ans[u],res);
 
    for(int v : g[u])   if (v != p && v != dig[u])  {
        //if (st.empty() || st.top() != u)
        //    add(u);
        dfs(v,u);
    }
    rem(dep[u]);
}
 
int ini(int u,int p)    {
    dep[u] = dep[p] + 1;
    dig[u] = u;
 
    MaxDep[u][0] = dep[u];
    MaxDep[u][1] = dep[u];
 
    for(int v : g[u])   if (v != p) {
        ini(v,u);
        upd(u,MaxDep[v][0]);
 
        if (MaxDep[u][0] == MaxDep[v][0])
            dig[u] = v;
    }
}
 
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    int n;  cin >> n;
    int m;  cin >> m;
 
    FOR(i,1,n)  {
        int x;  cin >> x;
        int y;  cin >> y;
 
        g[x].pb(y);
        g[y].pb(x);
    }
    FOR(i,1,n + 1)  cin >> c[i];
 
    Diameter::LamViecCanLam();
 
    ini(L,0);   dfs(L,0);
    ini(R,0);   dfs(R,0);
 
    FOR(i,1,n + 1)
        cout << ans[i] << "\n";
}

Compilation message

joi2019_ho_t5.cpp: In function 'int ini(int, int)':
joi2019_ho_t5.cpp:105:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 4.0

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

Subtask #2
0 / 32.0

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

Subtask #3
0 / 32.0

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