oj.uz

Submission #850657

# Submission time Handle Problem Language Result Execution time Memory
850657 2023-09-17T08:32:39 Z Hyojin Swapping Cities (APIO20_swap) C++17
100 / 100
 249 ms 62852 KB 
#include <bits/stdc++.h>
using namespace std;
#define bit(n,i) ((n>>i)&1) 
#define all(a) (a).begin(),(a).end()
#define pb push_back
#define ep emplace_back
#define pii pair<int,int>
#define piii pair<int,pii> 
#define fi first
#define se second
#define ll long long
#define debug(x) cerr << #x << ' ' << x << '\n'
#define dbg(x) cerr<<#x<<' '<<x<<' '
const int base=31;
const int MOD=1e9+7;
const int N=3e5+5;
int ans[N],value[N],lab[N],deg[N],p[N][20],depth[N],n,m;
bool ok[N];
vector<int>adj[N];
int find_set(int v)
{
	return (lab[v]==v?v:lab[v]=find_set(lab[v]));
}
void join(int u,int v,int w)
{
	lab[n]=n;
	value[n]=w;
	deg[u]++;
	deg[v]++;
	if (deg[u]>=3||deg[v]>=3) ok[n]=1;
	u=find_set(u);
	v=find_set(v);
	adj[n].pb(u);
	lab[u]=n;
	if (u!=v)
	{
		adj[n].pb(v);
		lab[v]=n;
	}
	ok[n]|=ok[u]|ok[v];
	++n;
}
int lca(int u,int v)
{
	if (depth[u]<depth[v]) swap(u,v);
	for (int i=18;~i;i--)
	{
		if (depth[u]-(1<<i)>=depth[v]) u=p[u][i];
	}
	if (u==v) return u;
	for (int i=18;~i;i--)
	{
		if (~p[u][i]&&p[u][i]!=p[v][i])
		{
			u=p[u][i];
			v=p[v][i];
		}
	}
	return p[u][0];
}
void dfs(int u,int par)
{
	if (ok[u]||adj[u].size()==1) ans[u]=value[u];
	else if (u!=par) ans[u]=ans[par];
	else ans[u]=-1;
	for (int v:adj[u])
	{
		if (v==par) continue;
		depth[v]=depth[u]+1;
		p[v][0]=u;
		dfs(v,u);
	}
}
void init(int N,int M,vector<int>U,vector<int>V,vector<int>W)
{
	memset(p,-1,sizeof p);
	n=N,m=M;
	for (int i=0;i<n;i++) lab[i]=i;
	vector<int>id;
	for (int i=0;i<m;i++) id.pb(i);
	sort(all(id),[&](int x,int y){return W[x]<W[y];});
	for (auto idx:id)
	{
		join(U[idx],V[idx],W[idx]);
	}
	dfs(n-1,n-1);
	for (int j=1;(1<<j)<n;j++)
	{
		for (int i=0;i<n;i++)
		{
			if (~p[i][j-1])
			{
				p[i][j]=p[p[i][j-1]][j-1];
			}
		}
	}
}
int getMinimumFuelCapacity(int X,int Y)
{
	return ans[lca(X,Y)];
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35420 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 5 ms 35428 KB Output is correct
4 Correct 5 ms 35672 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 5 ms 35420 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 6 ms 35524 KB Output is correct
9 Correct 51 ms 42188 KB Output is correct
10 Correct 62 ms 43872 KB Output is correct
11 Correct 62 ms 43812 KB Output is correct
12 Correct 68 ms 44148 KB Output is correct
13 Correct 62 ms 47308 KB Output is correct
14 Correct 60 ms 42696 KB Output is correct
15 Correct 133 ms 47836 KB Output is correct
16 Correct 128 ms 47652 KB Output is correct
17 Correct 131 ms 48100 KB Output is correct
18 Correct 170 ms 51348 KB Output is correct
19 Correct 66 ms 41944 KB Output is correct
20 Correct 158 ms 48652 KB Output is correct
21 Correct 131 ms 48920 KB Output is correct
22 Correct 181 ms 49452 KB Output is correct
23 Correct 168 ms 52392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35420 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 188 ms 54172 KB Output is correct
4 Correct 182 ms 54748 KB Output is correct
5 Correct 150 ms 54528 KB Output is correct
6 Correct 152 ms 54440 KB Output is correct
7 Correct 168 ms 54676 KB Output is correct
8 Correct 162 ms 54188 KB Output is correct
9 Correct 152 ms 54480 KB Output is correct
10 Correct 174 ms 54060 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35420 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 5 ms 35428 KB Output is correct
4 Correct 5 ms 35672 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 5 ms 35420 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 6 ms 35524 KB Output is correct
9 Correct 5 ms 35420 KB Output is correct
10 Correct 6 ms 35420 KB Output is correct
11 Correct 6 ms 35416 KB Output is correct
12 Correct 6 ms 35416 KB Output is correct
13 Correct 6 ms 35420 KB Output is correct
14 Correct 5 ms 35420 KB Output is correct
15 Correct 6 ms 35676 KB Output is correct
16 Correct 6 ms 35588 KB Output is correct
17 Correct 6 ms 35420 KB Output is correct
18 Correct 6 ms 35460 KB Output is correct
19 Correct 6 ms 35416 KB Output is correct
20 Correct 5 ms 35672 KB Output is correct
21 Correct 6 ms 35420 KB Output is correct
22 Correct 6 ms 35676 KB Output is correct
23 Correct 5 ms 35420 KB Output is correct
24 Correct 6 ms 35676 KB Output is correct
25 Correct 6 ms 35676 KB Output is correct
26 Correct 6 ms 35676 KB Output is correct
27 Correct 6 ms 35420 KB Output is correct
28 Correct 6 ms 35676 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35420 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 5 ms 35420 KB Output is correct
4 Correct 5 ms 35428 KB Output is correct
5 Correct 5 ms 35672 KB Output is correct
6 Correct 6 ms 35420 KB Output is correct
7 Correct 5 ms 35420 KB Output is correct
8 Correct 6 ms 35420 KB Output is correct
9 Correct 6 ms 35524 KB Output is correct
10 Correct 51 ms 42188 KB Output is correct
11 Correct 62 ms 43872 KB Output is correct
12 Correct 62 ms 43812 KB Output is correct
13 Correct 68 ms 44148 KB Output is correct
14 Correct 62 ms 47308 KB Output is correct
15 Correct 6 ms 35420 KB Output is correct
16 Correct 6 ms 35416 KB Output is correct
17 Correct 6 ms 35416 KB Output is correct
18 Correct 6 ms 35420 KB Output is correct
19 Correct 5 ms 35420 KB Output is correct
20 Correct 6 ms 35676 KB Output is correct
21 Correct 6 ms 35588 KB Output is correct
22 Correct 6 ms 35420 KB Output is correct
23 Correct 6 ms 35460 KB Output is correct
24 Correct 6 ms 35416 KB Output is correct
25 Correct 5 ms 35672 KB Output is correct
26 Correct 6 ms 35420 KB Output is correct
27 Correct 6 ms 35676 KB Output is correct
28 Correct 5 ms 35420 KB Output is correct
29 Correct 6 ms 35676 KB Output is correct
30 Correct 6 ms 35676 KB Output is correct
31 Correct 6 ms 35676 KB Output is correct
32 Correct 6 ms 35420 KB Output is correct
33 Correct 6 ms 35676 KB Output is correct
34 Correct 12 ms 36652 KB Output is correct
35 Correct 88 ms 43980 KB Output is correct
36 Correct 64 ms 43900 KB Output is correct
37 Correct 79 ms 43904 KB Output is correct
38 Correct 77 ms 43912 KB Output is correct
39 Correct 70 ms 43808 KB Output is correct
40 Correct 60 ms 42956 KB Output is correct
41 Correct 66 ms 44280 KB Output is correct
42 Correct 88 ms 43984 KB Output is correct
43 Correct 68 ms 48236 KB Output is correct
44 Correct 80 ms 44236 KB Output is correct
45 Correct 110 ms 53920 KB Output is correct
46 Correct 67 ms 43980 KB Output is correct
47 Correct 72 ms 44012 KB Output is correct
48 Correct 78 ms 47176 KB Output is correct
49 Correct 84 ms 57888 KB Output is correct
50 Correct 82 ms 52500 KB Output is correct
51 Correct 95 ms 51776 KB Output is correct
52 Correct 117 ms 53444 KB Output is correct
53 Correct 132 ms 54732 KB Output is correct
54 Correct 139 ms 59008 KB Output is correct
55 Correct 65 ms 47608 KB Output is correct
56 Correct 137 ms 56820 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35420 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 5 ms 35428 KB Output is correct
4 Correct 5 ms 35672 KB Output is correct
5 Correct 6 ms 35420 KB Output is correct
6 Correct 5 ms 35420 KB Output is correct
7 Correct 6 ms 35420 KB Output is correct
8 Correct 6 ms 35524 KB Output is correct
9 Correct 51 ms 42188 KB Output is correct
10 Correct 62 ms 43872 KB Output is correct
11 Correct 62 ms 43812 KB Output is correct
12 Correct 68 ms 44148 KB Output is correct
13 Correct 62 ms 47308 KB Output is correct
14 Correct 60 ms 42696 KB Output is correct
15 Correct 133 ms 47836 KB Output is correct
16 Correct 128 ms 47652 KB Output is correct
17 Correct 131 ms 48100 KB Output is correct
18 Correct 170 ms 51348 KB Output is correct
19 Correct 188 ms 54172 KB Output is correct
20 Correct 182 ms 54748 KB Output is correct
21 Correct 150 ms 54528 KB Output is correct
22 Correct 152 ms 54440 KB Output is correct
23 Correct 168 ms 54676 KB Output is correct
24 Correct 162 ms 54188 KB Output is correct
25 Correct 152 ms 54480 KB Output is correct
26 Correct 174 ms 54060 KB Output is correct
27 Correct 6 ms 35420 KB Output is correct
28 Correct 6 ms 35416 KB Output is correct
29 Correct 6 ms 35416 KB Output is correct
30 Correct 6 ms 35420 KB Output is correct
31 Correct 5 ms 35420 KB Output is correct
32 Correct 6 ms 35676 KB Output is correct
33 Correct 6 ms 35588 KB Output is correct
34 Correct 6 ms 35420 KB Output is correct
35 Correct 6 ms 35460 KB Output is correct
36 Correct 12 ms 36652 KB Output is correct
37 Correct 88 ms 43980 KB Output is correct
38 Correct 64 ms 43900 KB Output is correct
39 Correct 79 ms 43904 KB Output is correct
40 Correct 77 ms 43912 KB Output is correct
41 Correct 70 ms 43808 KB Output is correct
42 Correct 60 ms 42956 KB Output is correct
43 Correct 66 ms 44280 KB Output is correct
44 Correct 88 ms 43984 KB Output is correct
45 Correct 68 ms 48236 KB Output is correct
46 Correct 80 ms 44236 KB Output is correct
47 Correct 18 ms 36956 KB Output is correct
48 Correct 185 ms 48396 KB Output is correct
49 Correct 136 ms 48528 KB Output is correct
50 Correct 138 ms 48808 KB Output is correct
51 Correct 139 ms 48436 KB Output is correct
52 Correct 141 ms 47940 KB Output is correct
53 Correct 135 ms 46772 KB Output is correct
54 Correct 137 ms 49316 KB Output is correct
55 Correct 137 ms 48492 KB Output is correct
56 Correct 173 ms 51696 KB Output is correct
57 Correct 182 ms 49320 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 35420 KB Output is correct
2 Correct 5 ms 35420 KB Output is correct
3 Correct 5 ms 35420 KB Output is correct
4 Correct 5 ms 35428 KB Output is correct
5 Correct 5 ms 35672 KB Output is correct
6 Correct 6 ms 35420 KB Output is correct
7 Correct 5 ms 35420 KB Output is correct
8 Correct 6 ms 35420 KB Output is correct
9 Correct 6 ms 35524 KB Output is correct
10 Correct 51 ms 42188 KB Output is correct
11 Correct 62 ms 43872 KB Output is correct
12 Correct 62 ms 43812 KB Output is correct
13 Correct 68 ms 44148 KB Output is correct
14 Correct 62 ms 47308 KB Output is correct
15 Correct 60 ms 42696 KB Output is correct
16 Correct 133 ms 47836 KB Output is correct
17 Correct 128 ms 47652 KB Output is correct
18 Correct 131 ms 48100 KB Output is correct
19 Correct 170 ms 51348 KB Output is correct
20 Correct 188 ms 54172 KB Output is correct
21 Correct 182 ms 54748 KB Output is correct
22 Correct 150 ms 54528 KB Output is correct
23 Correct 152 ms 54440 KB Output is correct
24 Correct 168 ms 54676 KB Output is correct
25 Correct 162 ms 54188 KB Output is correct
26 Correct 152 ms 54480 KB Output is correct
27 Correct 174 ms 54060 KB Output is correct
28 Correct 6 ms 35420 KB Output is correct
29 Correct 6 ms 35416 KB Output is correct
30 Correct 6 ms 35416 KB Output is correct
31 Correct 6 ms 35420 KB Output is correct
32 Correct 5 ms 35420 KB Output is correct
33 Correct 6 ms 35676 KB Output is correct
34 Correct 6 ms 35588 KB Output is correct
35 Correct 6 ms 35420 KB Output is correct
36 Correct 6 ms 35460 KB Output is correct
37 Correct 12 ms 36652 KB Output is correct
38 Correct 88 ms 43980 KB Output is correct
39 Correct 64 ms 43900 KB Output is correct
40 Correct 79 ms 43904 KB Output is correct
41 Correct 77 ms 43912 KB Output is correct
42 Correct 70 ms 43808 KB Output is correct
43 Correct 60 ms 42956 KB Output is correct
44 Correct 66 ms 44280 KB Output is correct
45 Correct 88 ms 43984 KB Output is correct
46 Correct 68 ms 48236 KB Output is correct
47 Correct 80 ms 44236 KB Output is correct
48 Correct 18 ms 36956 KB Output is correct
49 Correct 185 ms 48396 KB Output is correct
50 Correct 136 ms 48528 KB Output is correct
51 Correct 138 ms 48808 KB Output is correct
52 Correct 139 ms 48436 KB Output is correct
53 Correct 141 ms 47940 KB Output is correct
54 Correct 135 ms 46772 KB Output is correct
55 Correct 137 ms 49316 KB Output is correct
56 Correct 137 ms 48492 KB Output is correct
57 Correct 173 ms 51696 KB Output is correct
58 Correct 182 ms 49320 KB Output is correct
59 Correct 66 ms 41944 KB Output is correct
60 Correct 158 ms 48652 KB Output is correct
61 Correct 131 ms 48920 KB Output is correct
62 Correct 181 ms 49452 KB Output is correct
63 Correct 168 ms 52392 KB Output is correct
64 Correct 6 ms 35416 KB Output is correct
65 Correct 5 ms 35672 KB Output is correct
66 Correct 6 ms 35420 KB Output is correct
67 Correct 6 ms 35676 KB Output is correct
68 Correct 5 ms 35420 KB Output is correct
69 Correct 6 ms 35676 KB Output is correct
70 Correct 6 ms 35676 KB Output is correct
71 Correct 6 ms 35676 KB Output is correct
72 Correct 6 ms 35420 KB Output is correct
73 Correct 6 ms 35676 KB Output is correct
74 Correct 110 ms 53920 KB Output is correct
75 Correct 67 ms 43980 KB Output is correct
76 Correct 72 ms 44012 KB Output is correct
77 Correct 78 ms 47176 KB Output is correct
78 Correct 84 ms 57888 KB Output is correct
79 Correct 82 ms 52500 KB Output is correct
80 Correct 95 ms 51776 KB Output is correct
81 Correct 117 ms 53444 KB Output is correct
82 Correct 132 ms 54732 KB Output is correct
83 Correct 139 ms 59008 KB Output is correct
84 Correct 65 ms 47608 KB Output is correct
85 Correct 137 ms 56820 KB Output is correct
86 Correct 55 ms 42468 KB Output is correct
87 Correct 157 ms 48472 KB Output is correct
88 Correct 157 ms 48548 KB Output is correct
89 Correct 180 ms 51528 KB Output is correct
90 Correct 163 ms 62408 KB Output is correct
91 Correct 164 ms 60256 KB Output is correct
92 Correct 177 ms 55836 KB Output is correct
93 Correct 206 ms 57244 KB Output is correct
94 Correct 249 ms 58780 KB Output is correct
95 Correct 222 ms 62852 KB Output is correct
96 Correct 186 ms 52100 KB Output is correct
97 Correct 217 ms 55864 KB Output is correct