oj.uz

Submission #916757

# Submission time Handle Problem Language Result Execution time Memory
916757 2024-01-26T13:30:18 Z GrindMachine Unique Cities (JOI19_ho_t5) C++17
64 / 100
 584 ms 63460 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
edi
https://codeforces.com/blog/entry/65042?#comment-491880

*/

const int MOD = 1e9 + 7;
const int N = 2e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> adj[N];
vector<ll> a(N);
pll diam = {-1,-1};

void dfs1(ll u, ll p, ll d){
    pll px = {d,u};
    amax(diam,px);
    trav(v,adj[u]){
        if(v == p) conts;
        dfs1(v,u,d+1);
    }
}

ll dis[N][2];
ll deepest[N][2];

void dfs2(ll u, ll p, ll t){
    trav(v,adj[u]){
        if(v == p) conts;
        dis[v][t] = dis[u][t]+1;
        dfs2(v,u,t);
        amax(deepest[u][t],deepest[v][t]+1);
    }
}

vector<ll> ans(N);
vector<ll> mx_without(N);
vector<ll> first_occ(N,inf2);
vector<pll> active(N);
ll siz = 0;

void dfs3(ll u, ll p, ll d, ll t){
    ll mx = deepest[u][t];
    ll cnt = upper_bound(active.begin(),active.begin()+siz,make_pair(d-mx,-1ll))-active.begin();
    if(dis[u][t] >= dis[u][t^1]){
        ans[u] = cnt;
    }

    mx = 0;
 
    trav(v,adj[u]){
        if(v == p) conts;
        mx_without[v] = mx;
        amax(mx,deepest[v][t]+1);
    }
 
    mx = 0;
    reverse(all(adj[u]));
 
    trav(v,adj[u]){
        if(v == p) conts;
        amax(mx_without[v],mx);
        amax(mx,deepest[v][t]+1);
    }
 
    reverse(all(adj[u]));
    
    trav(v,adj[u]){
        if(v == p) conts;
        mx = mx_without[v];
        ll new_siz = upper_bound(active.begin(),active.begin()+siz,make_pair(d-mx,-1ll))-active.begin();
        ll old_siz = siz;
        siz = new_siz;

        ll x = a[u];
        auto val1 = active[siz];
        auto val2 = first_occ[x];

        bool ins = false;

        if(first_occ[x] >= siz){
            ins = true;
            active[siz] = {d,u};
            first_occ[x] = siz;
            siz++;
        }

        dfs3(v,u,d+1,t);

        if(ins){
            siz--;
            active[siz] = val1;
            first_occ[x] = val2;
        }

        siz = old_siz;
    }
}

void solve(int test_case)
{
    ll n,m; cin >> n >> m;
    rep1(i,n-1){
        ll u,v; cin >> u >> v;
        adj[u].pb(v), adj[v].pb(u);
    }
    rep1(i,n) cin >> a[i];

    dfs1(1,-1,0);
    ll s = diam.ss;
    diam = {-1,-1};
    dfs1(s,-1,0);
    ll t = diam.ss;

    dfs2(s,-1,0);
    dfs2(t,-1,1);

    dfs3(s,-1,0,0);
    dfs3(t,-1,0,1);

    rep1(i,n){
        cout << ans[i] << endl;
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16476 KB Output is correct
2 Incorrect 7 ms 16476 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 94 ms 25348 KB Output is correct
2 Correct 155 ms 42888 KB Output is correct
3 Correct 23 ms 20816 KB Output is correct
4 Correct 330 ms 31316 KB Output is correct
5 Correct 409 ms 61504 KB Output is correct
6 Correct 364 ms 46160 KB Output is correct
7 Correct 236 ms 31280 KB Output is correct
8 Correct 288 ms 34644 KB Output is correct
9 Correct 349 ms 33692 KB Output is correct
10 Correct 261 ms 33364 KB Output is correct
11 Correct 142 ms 31936 KB Output is correct
12 Correct 359 ms 50768 KB Output is correct
13 Correct 377 ms 46280 KB Output is correct
14 Correct 332 ms 45072 KB Output is correct
15 Correct 116 ms 29620 KB Output is correct
16 Correct 324 ms 52176 KB Output is correct
17 Correct 372 ms 46384 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 29796 KB Output is correct
2 Correct 530 ms 61336 KB Output is correct
3 Correct 29 ms 21480 KB Output is correct
4 Correct 309 ms 32212 KB Output is correct
5 Correct 584 ms 63460 KB Output is correct
6 Correct 435 ms 47288 KB Output is correct
7 Correct 323 ms 32148 KB Output is correct
8 Correct 347 ms 38736 KB Output is correct
9 Correct 295 ms 36432 KB Output is correct
10 Correct 322 ms 34640 KB Output is correct
11 Correct 296 ms 32436 KB Output is correct
12 Correct 499 ms 57568 KB Output is correct
13 Correct 374 ms 45512 KB Output is correct
14 Correct 375 ms 45772 KB Output is correct
15 Correct 116 ms 30660 KB Output is correct
16 Correct 367 ms 53204 KB Output is correct
17 Correct 374 ms 47388 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16476 KB Output is correct
2 Incorrect 7 ms 16476 KB Output isn't correct
3 Halted 0 ms 0 KB -