oj.uz

Submission #100925

# Submission time Handle Problem Language Result Execution time Memory
100925 2019-03-15T08:36:03 Z Alexa2001 Unique Cities (JOI19_ho_t5) C++17
64 / 100
 895 ms 36852 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];
bool ap[Nmax];
vector<int> v[Nmax];
int n, M, nr;
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 cnt_dist(vector<int> &v)
{
    for(auto it : v) ap[tip[it]] = 1;

    int i, ans = 0;
    for(i=1; i<=M; ++i)
        if(ap[i])
        {
            ++ans;
            ap[i] = 0;
        }
    return ans;
}


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)
{

  /*  vector<int> see;
    for(i=0; i<stramos.size(); ++i)
        if(level[stramos[i]] <= level[node] - down[node])
            see.push_back(stramos[i]);
*/
    max_to(ans[node], bs(level[node] - down[node]));

    for(auto it : v[node])
        if(it != dad)
        {
         /*   vector<int> act = stramos;
            while(act.size() && level[act.back()] >= level[node] - max_ex[it]) act.pop_back();
            act.push_back(node);
        */

            int pos, val, lnr;
            pos = bs(level[node] - max_ex[it] - 1);
            lnr = nr;

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

            solve(it, node);

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

void Solve(int node)
{
    dfs(node);
    int i;
    for(i=0; i<=nr; ++i) S[i] = 0;
    nr = 0;
    solve(node);
}

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 8 ms 5120 KB Output is correct
2 Incorrect 8 ms 5248 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 267 ms 11212 KB Output is correct
2 Correct 465 ms 22148 KB Output is correct
3 Correct 54 ms 8056 KB Output is correct
4 Correct 506 ms 18656 KB Output is correct
5 Correct 822 ms 34940 KB Output is correct
6 Correct 729 ms 26652 KB Output is correct
7 Correct 547 ms 18676 KB Output is correct
8 Correct 552 ms 20320 KB Output is correct
9 Correct 596 ms 19704 KB Output is correct
10 Correct 695 ms 19576 KB Output is correct
11 Correct 321 ms 19412 KB Output is correct
12 Correct 848 ms 28616 KB Output is correct
13 Correct 628 ms 26568 KB Output is correct
14 Correct 710 ms 26056 KB Output is correct
15 Correct 258 ms 19240 KB Output is correct
16 Correct 683 ms 29808 KB Output is correct
17 Correct 782 ms 26712 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 13564 KB Output is correct
2 Correct 868 ms 35340 KB Output is correct
3 Correct 64 ms 8580 KB Output is correct
4 Correct 552 ms 19680 KB Output is correct
5 Correct 895 ms 36852 KB Output is correct
6 Correct 720 ms 27820 KB Output is correct
7 Correct 522 ms 19564 KB Output is correct
8 Correct 614 ms 22908 KB Output is correct
9 Correct 631 ms 21752 KB Output is correct
10 Correct 538 ms 20796 KB Output is correct
11 Correct 416 ms 19924 KB Output is correct
12 Correct 796 ms 33196 KB Output is correct
13 Correct 685 ms 26944 KB Output is correct
14 Correct 718 ms 26852 KB Output is correct
15 Correct 277 ms 20464 KB Output is correct
16 Correct 635 ms 31216 KB Output is correct
17 Correct 717 ms 27908 KB Output is correct

Subtask #4
0 / 32.0

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