oj.uz

Submission #773518

# Submission time Handle Problem Language Result Execution time Memory
773518 2023-07-05T06:25:55 Z 1bin Unique Cities (JOI19_ho_t5) C++14
4 / 100
 2000 ms 178672 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 2e5 + 5;
int n, m, C[NMAX], D[NMAX], a, b, mxd, ix, r1, r2, ans[NMAX], cur, cnt[NMAX];
vector<int> adj[NMAX];
vector<pair<int, int>> v[NMAX];

void dfs2(int x, int p, int d){
    if(d > mxd) mxd = d, ix = x;
    for(int&nx : adj[x])
        if(nx != p) dfs2(nx, x, d + 1);
    return;
}

void go(int x, int p){
    v[x].clear();
    for(int& nx : adj[x])
        if(nx != p){
            go(nx, x);
            v[x].emplace_back(v[nx][0].first + 1, nx);
        }
    v[x].emplace_back(0, x);
    sort(all(v[x])); reverse(all(v[x]));
    return;
}

void f(int x, int add){
    if(add){
        if(++cnt[C[x]] == 1) cur++;
    }
    else{
        if(--cnt[C[x]] == 0) cur--;
    }
    return;
}

stack<int> st;
void dfs(int x, int p, int d){
    stack<int> t;
    D[d] = x;
    for(int i = 0; i < v[x].size(); i++){
        int nx = v[x][i].second;
        int mxd = n + 1;
        if(i) mxd = d - v[x][0].first;
        else if(v[x].size() > 2) mxd = d - v[x][1].first;
        
        while(st.size() && st.top() >= mxd){
            f(D[st.top()], 0);
            t.emplace(st.top()); st.pop();
        }
        if(nx == x) ans[x] = max(ans[x], cur);
        else {
            st.emplace(d); f(x, 1);
            dfs(nx, x, d + 1);
            st.pop(); f(x, 0);
        }
    }
    
    while(t.size()){
        f(D[t.top()], 1);
        st.emplace(t.top()); t.pop();
    }
    return;
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for(int i = 1; i < n; i++){
        cin >> a >> b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }    
    for(int i = 1; i <= n; i++) cin >> C[i];
    dfs2(1, -1, 0);
    r1 = ix;
    mxd = 0; dfs2(r1, -1, 0);
    r2 = ix;
    
    go(r1, -1); dfs(r1, -1, 0);
    go(r2, -1); dfs(r2, -1, 0);
    for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
    return 0;
}

Compilation message

joi2019_ho_t5.cpp: In function 'void dfs(int, int, int)':
joi2019_ho_t5.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i = 0; i < v[x].size(); i++){
      |                    ~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 14 ms 10504 KB Output is correct
4 Correct 11 ms 10604 KB Output is correct
5 Correct 6 ms 9936 KB Output is correct
6 Correct 27 ms 11468 KB Output is correct
7 Correct 11 ms 10692 KB Output is correct
8 Correct 6 ms 9844 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 8 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 23 ms 11348 KB Output is correct
14 Correct 9 ms 10496 KB Output is correct
15 Correct 8 ms 10452 KB Output is correct
16 Correct 8 ms 9864 KB Output is correct
17 Correct 20 ms 10972 KB Output is correct
18 Correct 11 ms 10632 KB Output is correct
19 Correct 5 ms 9940 KB Output is correct
20 Correct 41 ms 11480 KB Output is correct
21 Correct 11 ms 10708 KB Output is correct
22 Correct 5 ms 9864 KB Output is correct
23 Correct 8 ms 10120 KB Output is correct
24 Correct 7 ms 10056 KB Output is correct
25 Correct 8 ms 9988 KB Output is correct
26 Correct 7 ms 9864 KB Output is correct
27 Correct 15 ms 11112 KB Output is correct
28 Correct 13 ms 10760 KB Output is correct
29 Correct 9 ms 10500 KB Output is correct
30 Correct 7 ms 9856 KB Output is correct
31 Correct 21 ms 10892 KB Output is correct
32 Correct 15 ms 10608 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 20480 KB Output is correct
2 Execution timed out 2073 ms 110228 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 25920 KB Output is correct
2 Execution timed out 2060 ms 178672 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 14 ms 10504 KB Output is correct
4 Correct 11 ms 10604 KB Output is correct
5 Correct 6 ms 9936 KB Output is correct
6 Correct 27 ms 11468 KB Output is correct
7 Correct 11 ms 10692 KB Output is correct
8 Correct 6 ms 9844 KB Output is correct
9 Correct 7 ms 10068 KB Output is correct
10 Correct 8 ms 10068 KB Output is correct
11 Correct 6 ms 9940 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 23 ms 11348 KB Output is correct
14 Correct 9 ms 10496 KB Output is correct
15 Correct 8 ms 10452 KB Output is correct
16 Correct 8 ms 9864 KB Output is correct
17 Correct 20 ms 10972 KB Output is correct
18 Correct 11 ms 10632 KB Output is correct
19 Correct 5 ms 9940 KB Output is correct
20 Correct 41 ms 11480 KB Output is correct
21 Correct 11 ms 10708 KB Output is correct
22 Correct 5 ms 9864 KB Output is correct
23 Correct 8 ms 10120 KB Output is correct
24 Correct 7 ms 10056 KB Output is correct
25 Correct 8 ms 9988 KB Output is correct
26 Correct 7 ms 9864 KB Output is correct
27 Correct 15 ms 11112 KB Output is correct
28 Correct 13 ms 10760 KB Output is correct
29 Correct 9 ms 10500 KB Output is correct
30 Correct 7 ms 9856 KB Output is correct
31 Correct 21 ms 10892 KB Output is correct
32 Correct 15 ms 10608 KB Output is correct
33 Correct 127 ms 20480 KB Output is correct
34 Execution timed out 2073 ms 110228 KB Time limit exceeded
35 Halted 0 ms 0 KB -