oj.uz

Submission #538543

# Submission time Handle Problem Language Result Execution time Memory
538543 2022-03-17T04:25:36 Z wiwiho Unique Cities (JOI19_ho_t5) C++14
4 / 100
 2000 ms 23092 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>
 
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;
 
const ll MOD = 1000000007;
const ll MAX = 2147483647;
 
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}
 
ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}
 
ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}
 
int n, m;
vector<vector<int>> g;
vector<int> C;
 
void init(){
    g.resize(n + 1);
    C.resize(n + 1);
}
 
int fd = -1, fv = -1;
void dfsfar(int now, int p, int d){
    if(d > fd) fd = d, fv = now;
    for(int i : g[now]){
        if(i == p) continue;
        dfsfar(i, now, d + 1);
    }
}
 
struct Solver{
 
    vector<int> dep, cnt, dis, ans;
    vector<int> st;
    int tans = 0;
 
    void add(int id){
        st.eb(id);
        cnt[C[id]]++;
        if(cnt[C[id]] == 1) tans++;
    }
    void remove(){
        int id = st.back();
        st.pob;
        cnt[C[id]]--;
        if(cnt[C[id]] == 0) tans--;
    }
 
    void dfs1(int now, int p, int d){
        dis[now] = d;
        for(int i : g[now]){
            if(i == p) continue;
            dfs1(i, now, d + 1);
            dep[now] = max(dep[i] + 1, dep[now]);
        }
    }
 
    void dfs2(int now, int p){
        int mx1 = -1, mx2 = -1;
        for(int i : g[now]){
            if(i == p) continue;
            if(mx1 == -1 || dep[i] > dep[mx1]) swap(mx1, i);
            if(i == -1) continue;
            if(mx2 == -1 || dep[i] > dep[mx2]) swap(mx2, i);
        }
        if(mx1 == -1){
            ans[now] = tans;
            return;
        }
 
        if(mx2 != -1){
            while(!st.empty() && dis[st.back()] >= dis[now] - dep[mx2] - 1) remove();
        }
        add(now);
        dfs2(mx1, now);
        if(!st.empty() && st.back() == now) remove();
 
        while(!st.empty() && dis[st.back()] >= dis[now] - dep[mx1] - 1) remove();
        add(now);
        for(int i : g[now]){
            if(i == p || i == mx1) continue;
            dfs2(i, now);
        }
        if(!st.empty() && st.back() == now) remove();
        //cerr << "dfs2 " << now << " " << mx1 << " " << mx2 << "\n";
        //printv(st, cerr);
        ans[now] = tans;
    }
 
    void solve(int s){
        cnt.resize(n + 1);
        dep.resize(n + 1);
        dis.resize(n + 1);
        ans.resize(n + 1);
 
        dfs1(s, s, 0);
        dfs2(s, s);
 
        /*cerr << "solve " << s << "\n";
        printv(dep, cerr);
        printv(dis, cerr);
        printv(ans, cerr);*/
    }
 
};

namespace BF{
    vector<int> dpt;
    void dfsbf(int now, int p){
        dpt[now] = now == p ? 0 : dpt[p] + 1;
        for(int i : g[now]){
            if(i == p) continue;
            dfsbf(i, now);
        }
    }

    int bf(int s){
        dpt.clear();
        dpt.resize(n + 1);
        dfsbf(s, s);
        vector<vector<int>> t(n + 1);
        vector<int> tv;
        for(int i = 1; i <= n; i++){
            t[dpt[i]].eb(i);
        }
        for(int i = 1; i <= n; i++){
            if(t[i].size() != 1) continue;
            tv.eb(C[t[i][0]]);
        }
        lsort(tv);
        uni(tv);
        return tv.size();
    }
}
 
int main(){
    StarBurstStream
 
    cin >> n >> m;
    init();
    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }
    for(int i = 1; i <= n; i++) cin >> C[i];
 
    dfsfar(1, 1, 0);
    int v1 = fv;
    fv = -1; fd = -1;
    dfsfar(v1, v1, 0);
    int v2 = fv;
    //cerr << v1 << " " << v2 << "\n";
 
    Solver s1, s2;
    s1.solve(v1);
    s2.solve(v2);
 
    for(int i = 1; i <= n; i++){
        cout << BF::bf(i) << "\n";
        //cout << max(s1.ans[i], s2.ans[i]) << "\n";
    }
 
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 147 ms 580 KB Output is correct
3 Correct 95 ms 552 KB Output is correct
4 Correct 234 ms 680 KB Output is correct
5 Correct 158 ms 600 KB Output is correct
6 Correct 368 ms 836 KB Output is correct
7 Correct 282 ms 692 KB Output is correct
8 Correct 117 ms 592 KB Output is correct
9 Correct 223 ms 604 KB Output is correct
10 Correct 196 ms 600 KB Output is correct
11 Correct 188 ms 596 KB Output is correct
12 Correct 82 ms 712 KB Output is correct
13 Correct 348 ms 952 KB Output is correct
14 Correct 235 ms 664 KB Output is correct
15 Correct 248 ms 656 KB Output is correct
16 Correct 76 ms 596 KB Output is correct
17 Correct 261 ms 764 KB Output is correct
18 Correct 253 ms 712 KB Output is correct
19 Correct 156 ms 596 KB Output is correct
20 Correct 416 ms 852 KB Output is correct
21 Correct 271 ms 824 KB Output is correct
22 Correct 121 ms 600 KB Output is correct
23 Correct 214 ms 612 KB Output is correct
24 Correct 192 ms 736 KB Output is correct
25 Correct 200 ms 596 KB Output is correct
26 Correct 83 ms 596 KB Output is correct
27 Correct 351 ms 780 KB Output is correct
28 Correct 273 ms 724 KB Output is correct
29 Correct 248 ms 672 KB Output is correct
30 Correct 67 ms 712 KB Output is correct
31 Correct 271 ms 764 KB Output is correct
32 Correct 291 ms 696 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2020 ms 16480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2060 ms 23092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 147 ms 580 KB Output is correct
3 Correct 95 ms 552 KB Output is correct
4 Correct 234 ms 680 KB Output is correct
5 Correct 158 ms 600 KB Output is correct
6 Correct 368 ms 836 KB Output is correct
7 Correct 282 ms 692 KB Output is correct
8 Correct 117 ms 592 KB Output is correct
9 Correct 223 ms 604 KB Output is correct
10 Correct 196 ms 600 KB Output is correct
11 Correct 188 ms 596 KB Output is correct
12 Correct 82 ms 712 KB Output is correct
13 Correct 348 ms 952 KB Output is correct
14 Correct 235 ms 664 KB Output is correct
15 Correct 248 ms 656 KB Output is correct
16 Correct 76 ms 596 KB Output is correct
17 Correct 261 ms 764 KB Output is correct
18 Correct 253 ms 712 KB Output is correct
19 Correct 156 ms 596 KB Output is correct
20 Correct 416 ms 852 KB Output is correct
21 Correct 271 ms 824 KB Output is correct
22 Correct 121 ms 600 KB Output is correct
23 Correct 214 ms 612 KB Output is correct
24 Correct 192 ms 736 KB Output is correct
25 Correct 200 ms 596 KB Output is correct
26 Correct 83 ms 596 KB Output is correct
27 Correct 351 ms 780 KB Output is correct
28 Correct 273 ms 724 KB Output is correct
29 Correct 248 ms 672 KB Output is correct
30 Correct 67 ms 712 KB Output is correct
31 Correct 271 ms 764 KB Output is correct
32 Correct 291 ms 696 KB Output is correct
33 Execution timed out 2020 ms 16480 KB Time limit exceeded
34 Halted 0 ms 0 KB -