oj.uz

Submission #532164

# Submission time Handle Problem Language Result Execution time Memory
532164 2022-03-02T08:00:13 Z syl123456 Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 32836 KB 
#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
template<typename T1>
void Debug(bool _split, T1 i) {
    if (_split)
        cerr << ", ";
    cerr << i;
}
template<typename T1, typename ...T2>
void Debug(bool _split, T1 i, T2 ...j) {
    if (_split)
        cerr << ", ";
    cerr << i;
    Debug(true, j...);
}
#define debug(args...) cout << "Line" << __LINE__ << " : [" << #args << "] is [", Debug(false, args), cerr << "]" << endl;
 
typedef pair<int, int> pi;
typedef long long ll;
 
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f;

const int N = 2e5;
 
vector<int> g[N];
int pa[N], c[N], at[N], cnt[N], ans[N];
pair<pi, pi> mx[N];
vector<pi> vv, stk;

int now;

pi dfs1(int i, int p) {
    pa[i] = p;
    pi res(0, i);
    for (int j : g[i])
        if (j != p) {
            pi tmp = dfs1(j, i);
            ++tmp.first;
            res = max(res, tmp);
        }
    return res;
}
 
int dfs2(int i, int p, int _v) {
    mx[i].first = mx[i].second = pi(0, i);
    for (int j : g[i])
        if (j != p) {
            pi tmp(dfs2(j, i, _v - 1) + 1, j);
            if (tmp.first > mx[i].first.first)
                mx[i].second = mx[i].first, mx[i].first = tmp;
            else if (tmp.first > mx[i].second.first)
                mx[i].second = tmp;
        }
    return mx[i].first.first;
}
 
void dfs3(int i, int p, int _v) {
    if (at[_v] == -2)
        at[_v] = c[i];
    else
        at[_v] = -1;
    for (int j : g[i])
        if (j != p)
            dfs3(j, i, _v + 1);
}

void add(int x, int y) {
    vv.emplace_back(x, y);
    if (vv.size() > N)
        exit(0);
    if (!cnt[y])
        ++now;
    ++cnt[y];
}

void del() {
    int y = vv.back().second;
    vv.pop_back();
    --cnt[y];
    if (!cnt[y])
        --now;
}
 
void dfs4(int i, int p, int _v) {

    int tmp;
    if (mx[i].first.first > 0)
        tmp = _v + mx[i].first.first;
    else
        tmp = _v;
 
    int st = stk.size();

    while (vv.back().first <= tmp)
        stk.push_back(vv.back()), del();
    
    if (stk.size() > N)
        exit(0);
        
    ans[i] = now;

    add(_v, c[i]);
    
    for (int j : g[i])
        if (j != p && j != mx[i].first.second)
            dfs4(j, i, _v - 1);

    del();
 
    if (mx[i].first.second != i) {
        if (mx[i].second.first > 0)
            tmp = _v + mx[i].second.first;
        else
            tmp = _v;
        
        while (stk.size() > st && stk.back().first > tmp)
            add(stk.back().first, stk.back().second), stk.pop_back();
 
        add(_v, c[i]);
        
        dfs4(mx[i].first.second, i, _v - 1);

        del();
    }
 
    while (stk.size() > st)
        add(stk.back().first, stk.back().second), stk.pop_back();
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, _;
    cin >> n >> _;
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y), g[y].push_back(x);
    }
    for (int i = 0; i < n; ++i)
        cin >> c[i], --c[i];
    int x = dfs1(0, -1).second;
    int y = dfs1(x, -1).second;
    vector<int> dm;
    for (int i = y; ~i; i = pa[i])
        dm.push_back(i);

    x = dm.size() - 1 >> 1;//2k -> k-1, 2k+1 -> k
    dfs2(dm[x], dm[x + 1], 0);
    fill(at, at + n, -2);
    dfs3(dm[x + 1], dm[x], 1);
    fill(cnt, cnt + n, 0);
    now = 0;
    vv.emplace_back(inf, -1);
    for (int i = n - 1; i; --i)
        if (at[i] >= 0) {
            add(i, at[i]);
        }
    dfs4(dm[x], dm[x + 1], 0);
 
    x = dm.size() >> 1;//2k -> k, 2k+1 -> k
    dfs2(dm[x], dm[x - 1], 0);
    fill(at, at + n, -2);
    dfs3(dm[x - 1], dm[x], 1);
    fill(cnt, cnt + n, 0);
    now = 0;
    vv.clear();
    vv.emplace_back(inf, -1);
    for (int i = n - 1; i; --i)
        if (at[i] >= 0) {
            add(i, at[i]);
        }
    dfs4(dm[x], dm[x - 1], 0);
 
    for (int i = 0; i < n; ++i)
        cout << ans[i] << '\n';
}

Compilation message

joi2019_ho_t5.cpp: In function 'void dfs4(int, int, int)':
joi2019_ho_t5.cpp:118:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |         while (stk.size() > st && stk.back().first > tmp)
      |                ~~~~~~~~~~~^~~~
joi2019_ho_t5.cpp:128:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  128 |     while (stk.size() > st)
      |            ~~~~~~~~~~~^~~~
joi2019_ho_t5.cpp: In function 'int main()':
joi2019_ho_t5.cpp:150:19: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  150 |     x = dm.size() - 1 >> 1;//2k -> k-1, 2k+1 -> k
      |         ~~~~~~~~~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 8 ms 5068 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 12 ms 5336 KB Output is correct
7 Correct 6 ms 5252 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 3 ms 5068 KB Output is correct
13 Correct 15 ms 5320 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 3 ms 5068 KB Output is correct
17 Correct 10 ms 5300 KB Output is correct
18 Correct 6 ms 5196 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 16 ms 5324 KB Output is correct
21 Correct 7 ms 5196 KB Output is correct
22 Correct 4 ms 5068 KB Output is correct
23 Correct 4 ms 5196 KB Output is correct
24 Correct 4 ms 5120 KB Output is correct
25 Correct 5 ms 5068 KB Output is correct
26 Correct 4 ms 5068 KB Output is correct
27 Correct 8 ms 5196 KB Output is correct
28 Correct 8 ms 5196 KB Output is correct
29 Correct 5 ms 5196 KB Output is correct
30 Correct 3 ms 5068 KB Output is correct
31 Correct 8 ms 5196 KB Output is correct
32 Correct 6 ms 5196 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 12900 KB Output is correct
2 Execution timed out 2083 ms 21296 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 16004 KB Output is correct
2 Execution timed out 2085 ms 32836 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4940 KB Output is correct
2 Correct 3 ms 5068 KB Output is correct
3 Correct 8 ms 5068 KB Output is correct
4 Correct 6 ms 5240 KB Output is correct
5 Correct 3 ms 5068 KB Output is correct
6 Correct 12 ms 5336 KB Output is correct
7 Correct 6 ms 5252 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5068 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 3 ms 5068 KB Output is correct
13 Correct 15 ms 5320 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 3 ms 5068 KB Output is correct
17 Correct 10 ms 5300 KB Output is correct
18 Correct 6 ms 5196 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 16 ms 5324 KB Output is correct
21 Correct 7 ms 5196 KB Output is correct
22 Correct 4 ms 5068 KB Output is correct
23 Correct 4 ms 5196 KB Output is correct
24 Correct 4 ms 5120 KB Output is correct
25 Correct 5 ms 5068 KB Output is correct
26 Correct 4 ms 5068 KB Output is correct
27 Correct 8 ms 5196 KB Output is correct
28 Correct 8 ms 5196 KB Output is correct
29 Correct 5 ms 5196 KB Output is correct
30 Correct 3 ms 5068 KB Output is correct
31 Correct 8 ms 5196 KB Output is correct
32 Correct 6 ms 5196 KB Output is correct
33 Correct 105 ms 12900 KB Output is correct
34 Execution timed out 2083 ms 21296 KB Time limit exceeded
35 Halted 0 ms 0 KB -