oj.uz

Submission #100926

# Submission time Handle Problem Language Result Execution time Memory
100926 2019-03-15T08:55:14 Z Alexa2001 Unique Cities (JOI19_ho_t5) C++17
0 / 100
 2000 ms 54472 KB 
#include <bits/stdc++.h>

using namespace std;


const int Nmax = 2e5 + 5;

int down[Nmax], ans[Nmax], level[Nmax], st[Nmax], max_ex[Nmax], cnt[Nmax];
bool ap[Nmax];
vector<int> v[Nmax], collect_ans[Nmax], edge[Nmax];
int n, M, nr, Distincte;
int tip[Nmax], S[Nmax];


void read()
{
    int i, x, y;
    cin >> n >> M;
    for(i=1; i<n; ++i)
    {
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }

    for(i=1; i<=n; ++i) cin >> tip[i];
}

void print_sol()
{
    int i;
    for(i=1; i<=n; ++i) cout << min(M, ans[i]) << '\n';
}

void max_to(int &x, int y) { if(x < y) x = y; }


void dfs0(int node, int dad = 0)
{
    level[node] = level[dad] + 1;
    for(auto it : v[node])
        if(it != dad)
            dfs0(it, node);
}

pair<int,int> diametru()
{
    int i, A = 1, B = 1;

    dfs0(1);
    for(i=1; i<=n; ++i)
        if(level[i] > level[A]) A = i;

    dfs0(A);
    for(i=1; i<=n; ++i)
        if(level[i] > level[B]) B = i;

    return {A, B};
}

void dfs(int node, int dad = 0)
{
    down[node] = 1;
    level[node] = level[dad] + 1;

    for(auto it : v[node])
        if(it != dad)
        {
            dfs(it, node);
            down[node] = max(down[node], down[it] + 1);
        }

    int i, mx = 0;
    for(i=0; i<v[node].size(); ++i)
        if(v[node][i] != dad)
        {
            max_ex[v[node][i]] = mx;
            max_to(mx, down[v[node][i]]);
        }

    mx = 0;
    for(i=v[node].size()-1; i>=0; --i)
        if(v[node][i] != dad)
        {
            max_to(max_ex[v[node][i]], mx);
            max_to(mx, down[v[node][i]]);
        }
}

int bs(int val)
{
    int st = 1, dr = nr, mid;

    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(level[S[mid]] <= val) st = mid + 1;
            else dr = mid - 1;
    }
    return dr;
}

void solve(int node, int dad = 0)
{
    collect_ans[S[bs(level[node] - down[node])]].push_back(node);

    for(auto it : v[node])
        if(it != dad)
        {
            int pos, val, lnr;
            pos = bs(level[node] - max_ex[it] - 1);
            lnr = nr;

            edge[S[pos]].push_back(node);

            val = S[pos+1];
            S[pos+1] = node;
            nr = pos+1;

            solve(it, node);

            S[pos+1] = val;
            nr = lnr;
        }
}

void extract_ans(int node)
{
    bool ok = 0;

    if(!ap[tip[node]])
    {
        ok = 1;
        ap[tip[node]] = 1;
        ++Distincte;
    }

    for(auto it : collect_ans[node])
        max_to(ans[it], Distincte);

    for(auto it : edge[node])
        extract_ans(it);

    if(ok)
    {
        ap[tip[node]] = 0;
        --Distincte;
    }
}

void Solve(int node)
{
    dfs(node);
    int i;
    for(i=0; i<=nr; ++i) S[i] = 0;
    nr = 0;
    for(i=0; i<=n; ++i) edge[i].clear(), collect_ans[i].clear();

    solve(node);
    for(auto it : edge[0]) extract_ans(it);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    read();
    auto P = diametru();

    Solve(P.first);
    Solve(P.second);

    print_sol();

    return 0;
}

Compilation message

joi2019_ho_t5.cpp: In function 'void dfs(int, int)':
joi2019_ho_t5.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14464 KB Output is correct
2 Incorrect 19 ms 14592 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 24104 KB Output is correct
2 Correct 604 ms 37492 KB Output is correct
3 Correct 77 ms 18424 KB Output is correct
4 Correct 681 ms 31376 KB Output is correct
5 Correct 1140 ms 54472 KB Output is correct
6 Correct 1183 ms 41964 KB Output is correct
7 Execution timed out 2041 ms 29680 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14464 KB Output is correct
2 Incorrect 19 ms 14592 KB Output isn't correct
3 Halted 0 ms 0 KB -