oj.uz

Submission #828277

# Submission time Handle Problem Language Result Execution time Memory
828277 2023-08-17T07:36:09 Z Evirir Cat Exercise (JOI23_ho_t4) C++17
100 / 100
 262 ms 55736 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;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define cbug if(DEBUG) cout
#define setp(x) cout<<fixed<<setprecision(x)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
//template<typename T>
//using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
ostream& operator<<(ostream &out, ii x){ out<<"("<<x.F<<","<<x.S<<")"; return out; }
template<typename T> void amax(T &a, T b){ a=max(a,b); }
template<typename T> void amin(T &a, T b){ a=min(a,b); }
struct Hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const ll INF = ll(1e18);
const int MOD = 998244353;
const bool DEBUG = 0;
const int MAXN = 200005;
const int LG = 21;

struct DSU {
	struct Node{ int p, sz, mx; };
	vector<Node> dsu; int cc;
	Node& operator[](int id){ return dsu[rt(id)]; }
	DSU(int n){ dsu.resize(n);
		forn(i,0,n){ cc=n; dsu[i]={i,1,i}; }
	}
	inline int rt(int u){ return (dsu[u].p==u) ? u : dsu[u].p=rt(dsu[u].p); }
	inline bool sameset(int u, int v){ return rt(u)==rt(v); }
	void merge(int u, int v){
		u = rt(u); v = rt(v);
		if(u == v) return;
		if(dsu[u].sz < dsu[v].sz) swap(u,v);
		dsu[v].p = u;
		dsu[u].sz += dsu[v].sz;
        dsu[u].mx = max(dsu[u].mx, dsu[v].mx);
		cc--;
	}
};

vector<vector<int>> adj;
vector<ll> dist;
vector<ll> dp;
vector<bool> vst;

int in[MAXN],out[MAXN],tmr=-1;
int prt[LG][MAXN];
int dep[MAXN];

void dfs_lca(int u, int p)
{
	in[u]=++tmr;
	prt[0][u]=p;
	forn(i,1,LG){
		if(prt[i-1][u]!=-1) prt[i][u]=prt[i-1][prt[i-1][u]];
	}
	for(int v: adj[u]){
		if(v==p) continue;
        dep[v] = dep[u] + 1;
		dfs_lca(v,u);
	}
	out[u]=tmr;
}
bool isChild(int u, int v)
{
	return in[u]<=in[v] && out[v]<=out[u];
}
int getLca(int u, int v)
{
	if(isChild(u,v)) return u;
	for(int i=LG-1;i>=0;i--){
		if(prt[i][u]!=-1 && !isChild(prt[i][u],v))
			u=prt[i][u];
	}
	return prt[0][u];
}

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    mset(prt,-1);

    int n; cin>>n;
    adj.resize(n);
    dp.resize(n, 0);
    vst.resize(n, 0);
    dist.resize(n);

    int p[n];
    forn(i,0,n)
    {
        cin>>p[i];
        p[i]--;
    }
    forn(i,0,n-1)
    {
        int u,v; cin>>u>>v; u--; v--;
        u=p[u];
        v=p[v];
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs_lca(0, -1);
    DSU dsu(n);
    forn(u,0,n)
    {
        for (int v : adj[u])
        {
            if (v > u) continue;
            int mx = dsu[v].mx;
            int dist = dep[u] + dep[mx] - 2 * dep[getLca(u, mx)];
            dp[u] = max(dp[u], dp[mx] + dist);
        }
        for (int v : adj[u])
        {
            if (v > u) continue;
            dsu.merge(u, v);
        }
    }

    cout<<dp[n-1]<<'\n';

    return 0;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16776 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16684 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16776 KB Output is correct
6 Correct 9 ms 16780 KB Output is correct
7 Correct 8 ms 16768 KB Output is correct
8 Correct 7 ms 16780 KB Output is correct
9 Correct 9 ms 16724 KB Output is correct
10 Correct 7 ms 16776 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16776 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16684 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16776 KB Output is correct
6 Correct 9 ms 16780 KB Output is correct
7 Correct 8 ms 16768 KB Output is correct
8 Correct 7 ms 16780 KB Output is correct
9 Correct 9 ms 16724 KB Output is correct
10 Correct 7 ms 16776 KB Output is correct
11 Correct 8 ms 16744 KB Output is correct
12 Correct 7 ms 16764 KB Output is correct
13 Correct 8 ms 16724 KB Output is correct
14 Correct 7 ms 16812 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 8 ms 16776 KB Output is correct
17 Correct 7 ms 16788 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16776 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16684 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16776 KB Output is correct
6 Correct 9 ms 16780 KB Output is correct
7 Correct 8 ms 16768 KB Output is correct
8 Correct 7 ms 16780 KB Output is correct
9 Correct 9 ms 16724 KB Output is correct
10 Correct 7 ms 16776 KB Output is correct
11 Correct 8 ms 16744 KB Output is correct
12 Correct 7 ms 16764 KB Output is correct
13 Correct 8 ms 16724 KB Output is correct
14 Correct 7 ms 16812 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 8 ms 16776 KB Output is correct
17 Correct 7 ms 16788 KB Output is correct
18 Correct 9 ms 17500 KB Output is correct
19 Correct 9 ms 17620 KB Output is correct
20 Correct 9 ms 17620 KB Output is correct
21 Correct 9 ms 17560 KB Output is correct
22 Correct 9 ms 17648 KB Output is correct
23 Correct 12 ms 17576 KB Output is correct
24 Correct 12 ms 17684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16776 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16684 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16776 KB Output is correct
6 Correct 9 ms 16780 KB Output is correct
7 Correct 8 ms 16768 KB Output is correct
8 Correct 7 ms 16780 KB Output is correct
9 Correct 9 ms 16724 KB Output is correct
10 Correct 7 ms 16776 KB Output is correct
11 Correct 8 ms 16744 KB Output is correct
12 Correct 7 ms 16764 KB Output is correct
13 Correct 8 ms 16724 KB Output is correct
14 Correct 7 ms 16812 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 8 ms 16776 KB Output is correct
17 Correct 7 ms 16788 KB Output is correct
18 Correct 9 ms 17500 KB Output is correct
19 Correct 9 ms 17620 KB Output is correct
20 Correct 9 ms 17620 KB Output is correct
21 Correct 9 ms 17560 KB Output is correct
22 Correct 9 ms 17648 KB Output is correct
23 Correct 12 ms 17576 KB Output is correct
24 Correct 12 ms 17684 KB Output is correct
25 Correct 7 ms 16724 KB Output is correct
26 Correct 9 ms 17612 KB Output is correct
27 Correct 9 ms 17560 KB Output is correct
28 Correct 10 ms 17556 KB Output is correct
29 Correct 9 ms 17492 KB Output is correct
30 Correct 13 ms 17376 KB Output is correct
31 Correct 12 ms 17308 KB Output is correct
32 Correct 12 ms 17324 KB Output is correct
33 Correct 9 ms 17304 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16776 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16684 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16776 KB Output is correct
6 Correct 9 ms 16780 KB Output is correct
7 Correct 8 ms 16768 KB Output is correct
8 Correct 7 ms 16780 KB Output is correct
9 Correct 9 ms 16724 KB Output is correct
10 Correct 7 ms 16776 KB Output is correct
11 Correct 8 ms 16744 KB Output is correct
12 Correct 7 ms 16764 KB Output is correct
13 Correct 8 ms 16724 KB Output is correct
14 Correct 7 ms 16812 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 8 ms 16776 KB Output is correct
17 Correct 7 ms 16788 KB Output is correct
18 Correct 9 ms 17500 KB Output is correct
19 Correct 9 ms 17620 KB Output is correct
20 Correct 9 ms 17620 KB Output is correct
21 Correct 9 ms 17560 KB Output is correct
22 Correct 9 ms 17648 KB Output is correct
23 Correct 12 ms 17576 KB Output is correct
24 Correct 12 ms 17684 KB Output is correct
25 Correct 108 ms 47840 KB Output is correct
26 Correct 162 ms 55736 KB Output is correct
27 Correct 123 ms 55728 KB Output is correct
28 Correct 251 ms 54960 KB Output is correct
29 Correct 262 ms 48076 KB Output is correct
30 Correct 223 ms 53056 KB Output is correct
31 Correct 240 ms 51532 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16692 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Correct 204 ms 40020 KB Output is correct
4 Correct 183 ms 39948 KB Output is correct
5 Correct 159 ms 39984 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16776 KB Output is correct
2 Correct 7 ms 16708 KB Output is correct
3 Correct 8 ms 16684 KB Output is correct
4 Correct 8 ms 16724 KB Output is correct
5 Correct 9 ms 16776 KB Output is correct
6 Correct 9 ms 16780 KB Output is correct
7 Correct 8 ms 16768 KB Output is correct
8 Correct 7 ms 16780 KB Output is correct
9 Correct 9 ms 16724 KB Output is correct
10 Correct 7 ms 16776 KB Output is correct
11 Correct 8 ms 16744 KB Output is correct
12 Correct 7 ms 16764 KB Output is correct
13 Correct 8 ms 16724 KB Output is correct
14 Correct 7 ms 16812 KB Output is correct
15 Correct 7 ms 16724 KB Output is correct
16 Correct 8 ms 16776 KB Output is correct
17 Correct 7 ms 16788 KB Output is correct
18 Correct 9 ms 17500 KB Output is correct
19 Correct 9 ms 17620 KB Output is correct
20 Correct 9 ms 17620 KB Output is correct
21 Correct 9 ms 17560 KB Output is correct
22 Correct 9 ms 17648 KB Output is correct
23 Correct 12 ms 17576 KB Output is correct
24 Correct 12 ms 17684 KB Output is correct
25 Correct 7 ms 16724 KB Output is correct
26 Correct 9 ms 17612 KB Output is correct
27 Correct 9 ms 17560 KB Output is correct
28 Correct 10 ms 17556 KB Output is correct
29 Correct 9 ms 17492 KB Output is correct
30 Correct 13 ms 17376 KB Output is correct
31 Correct 12 ms 17308 KB Output is correct
32 Correct 12 ms 17324 KB Output is correct
33 Correct 9 ms 17304 KB Output is correct
34 Correct 108 ms 47840 KB Output is correct
35 Correct 162 ms 55736 KB Output is correct
36 Correct 123 ms 55728 KB Output is correct
37 Correct 251 ms 54960 KB Output is correct
38 Correct 262 ms 48076 KB Output is correct
39 Correct 223 ms 53056 KB Output is correct
40 Correct 240 ms 51532 KB Output is correct
41 Correct 8 ms 16692 KB Output is correct
42 Correct 7 ms 16724 KB Output is correct
43 Correct 204 ms 40020 KB Output is correct
44 Correct 183 ms 39948 KB Output is correct
45 Correct 159 ms 39984 KB Output is correct
46 Correct 158 ms 51088 KB Output is correct
47 Correct 181 ms 51068 KB Output is correct
48 Correct 195 ms 51092 KB Output is correct
49 Correct 135 ms 51084 KB Output is correct
50 Correct 251 ms 40200 KB Output is correct
51 Correct 241 ms 40328 KB Output is correct
52 Correct 248 ms 40260 KB Output is correct
53 Correct 231 ms 40200 KB Output is correct