Submission #163814

#	Time	Username	Problem	Language	Result	Execution time	Memory
163814		combi1k1	Unique Cities (JOI19_ho_t5)	C++14	100 / 100	563 ms	38192 KiB

joi2019_ho_t5

#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";
}
/*
10 10
2 6
5 8
10 8
1 4
10 6
4 5
10 7
6 9
3 7
1 2 3 4 5 6 7 8 9 10
*/

Compilation message (stderr)

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: 4 / 4
• Subtask 2: 32 / 32
• Subtask 3: 32 / 32
• Subtask 4: 32 / 32