oj.uz

Submission #679550

# Submission time Handle Problem Language Result Execution time Memory
679550 2023-01-08T13:31:18 Z Dan4Life Swapping Cities (APIO20_swap) C++17
6 / 100
 596 ms 173572 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back

const int maxn = (int)1e6+10;
const int lgn = 31;

int n, m, num;
bool good[maxn];
int jmp[lgn][maxn], goodd[lgn][maxn];
vector<int> adj[maxn];
struct Edge{ int u, v, w; };
int p[maxn], lev[maxn], wei[maxn], deg[maxn];

Edge edge[maxn];

int getPath(int x, int steps){
	for(int i = lgn-1; i >= 0; i--)
		if(steps&(1<<i) and x!=-1) x = jmp[i][x];
	return x; 
}

int lca(int a, int b){
	if(a==b) return a;
	if(jmp[0][a]==jmp[0][b]) return jmp[0][a];
	if(lev[a] < lev[b]) swap(a,b);
	a = getPath(a, lev[a]-lev[b]);
	for(int i = lgn-1; i >= 0; i--)
		if(jmp[i][a]!=-1 and jmp[i][a]!=jmp[i][b])
			a = jmp[i][a], b = jmp[i][b];
	return lca(a,b);
}

int findSet(int i){ return p[i]==i?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j) { return findSet(i)==findSet(j); }

void unionSet(Edge &e){
	int i = e.u, j = e.v;
	deg[i]++, deg[j]++;
	bool chk = (deg[i]>=3 or deg[j]>=3);
	int x = findSet(i), y = findSet(j);
	if(x!=y) adj[num].pb(y);
	adj[num].pb(x); p[x]=p[y]=num;
	good[num] |= good[x]|good[y]|chk|(x==y);
	wei[num] = e.w; num++;
}

void dfs(int s, int p){
	if(p!=-1) lev[s] = lev[p]+1, jmp[0][s] = p; 
	goodd[0][s] = good[s]; 
	for(auto u : adj[s]) if(u!=p) dfs(u,s);
}

void init(int N, int M, vector<int> u, vector<int> v, vector<int> w) {
	n = N, m = M; num = n; memset(jmp,-1,sizeof(jmp));
	for(int i = 0; i < n+m; i++) p[i] = i;
	for(int i = 0; i < m; i++) edge[i] = {u[i],v[i],w[i]};
	sort(edge,edge+m,[&](Edge &x, Edge &y){ return x.w<y.w; });
	for(int i = 0; i < m; i++) unionSet(edge[i]);
	dfs(num-1,-1);
	for(int i = 1; i < lgn; i++)
		for(int j = 0; j+(1<<i)-1 < num; j++)
			if(jmp[i-1][j]!=-1) jmp[i][j] = jmp[i-1][jmp[i-1][j]];
	for(int i = 1; i < lgn; i++)
		for(int j = 0; j+(1<<i)-1 < num; j++)
			goodd[i][j] = goodd[i-1][j] | goodd[i-1][goodd[i-1][j]];
}

int getMinimumFuelCapacity(int x, int y) {
	int z = lca(x,y);
	for(int i = lgn-1; i >= 0; i--) 
		if(jmp[i][z]!=-1 and !goodd[i][z]) z = jmp[i][z];
	if(good[z]) return wei[z];
	if(jmp[0][z]!=-1) z=jmp[0][z];
	return good[z]?wei[z]:-1;
}

/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1
*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 145228 KB Output is correct
2 Correct 54 ms 145160 KB Output is correct
3 Correct 57 ms 145116 KB Output is correct
4 Correct 58 ms 145268 KB Output is correct
5 Correct 56 ms 145356 KB Output is correct
6 Correct 56 ms 145260 KB Output is correct
7 Correct 57 ms 145324 KB Output is correct
8 Correct 56 ms 145396 KB Output is correct
9 Correct 106 ms 162420 KB Output is correct
10 Correct 136 ms 166660 KB Output is correct
11 Correct 123 ms 166164 KB Output is correct
12 Correct 124 ms 167364 KB Output is correct
13 Correct 122 ms 169720 KB Output is correct
14 Correct 119 ms 162568 KB Output is correct
15 Correct 283 ms 168428 KB Output is correct
16 Correct 287 ms 167804 KB Output is correct
17 Correct 301 ms 169148 KB Output is correct
18 Correct 490 ms 171496 KB Output is correct
19 Correct 143 ms 151872 KB Output is correct
20 Correct 266 ms 169716 KB Output is correct
21 Correct 291 ms 169080 KB Output is correct
22 Correct 294 ms 170568 KB Output is correct
23 Correct 487 ms 172904 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 145228 KB Output is correct
2 Correct 54 ms 145160 KB Output is correct
3 Incorrect 596 ms 173572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 145228 KB Output is correct
2 Correct 54 ms 145160 KB Output is correct
3 Correct 57 ms 145116 KB Output is correct
4 Correct 58 ms 145268 KB Output is correct
5 Correct 56 ms 145356 KB Output is correct
6 Correct 56 ms 145260 KB Output is correct
7 Correct 57 ms 145324 KB Output is correct
8 Correct 56 ms 145396 KB Output is correct
9 Incorrect 56 ms 145172 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 145172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 145228 KB Output is correct
2 Correct 54 ms 145160 KB Output is correct
3 Correct 57 ms 145116 KB Output is correct
4 Correct 58 ms 145268 KB Output is correct
5 Correct 56 ms 145356 KB Output is correct
6 Correct 56 ms 145260 KB Output is correct
7 Correct 57 ms 145324 KB Output is correct
8 Correct 56 ms 145396 KB Output is correct
9 Correct 106 ms 162420 KB Output is correct
10 Correct 136 ms 166660 KB Output is correct
11 Correct 123 ms 166164 KB Output is correct
12 Correct 124 ms 167364 KB Output is correct
13 Correct 122 ms 169720 KB Output is correct
14 Correct 119 ms 162568 KB Output is correct
15 Correct 283 ms 168428 KB Output is correct
16 Correct 287 ms 167804 KB Output is correct
17 Correct 301 ms 169148 KB Output is correct
18 Correct 490 ms 171496 KB Output is correct
19 Incorrect 596 ms 173572 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 145172 KB Output isn't correct
2 Halted 0 ms 0 KB -