oj.uz

Submission #836616

# Submission time Handle Problem Language Result Execution time Memory
836616 2023-08-24T13:25:42 Z Baytoro Fountain Parks (IOI21_parks) C++17
5 / 100
 697 ms 57268 KB 
#include "parks.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define fr first
#define sc second
const int N=2e5+5;
vector<array<int,3>> g[N];
int p[N];
vector<int> sz(N,1);
int f(int x){
	if(p[x]==x) return x;
	return p[x]=f(p[x]);
}
bool add(int a, int b){
	a=f(a);
	b=f(b);
	if(a==b) return 0;
	if(rand()%2) swap(a,b);//<-может лагать
	p[a]=b;
	sz[b]+=sz[a];
	return 1;
}
void add_edge(int a, int b, int u, int v){
	g[a].pb({b,u,v});
	g[b].pb({a,u,v});
}
int construct_roads(vector<int> x, vector<int> y) {
	int n=x.size();
	map<pair<int,int>,int> X,Y;
	for(int i=0;i<n;i++){
		p[i]=i;
		X[{x[i],y[i]}]=i;
	}
	vector<int> u,v,a,b;
	for(int i=0;i<n;i++){
		if(X.count({x[i]-2,y[i]})){
			int j=X[{x[i]-2,y[i]}];
			if(add(i,j)){
				u.pb(i);v.pb(j);
				a.pb(-1);b.pb(-1);
				int A=u.size()-1;
				if(Y.count({x[i]-1,y[i]-1})){
					int B=Y[{x[i]-1,y[i]-1}];
					add_edge(A,B,x[i]-1,y[i]-1);
					Y.erase({x[i]-1,y[i]-1});
				}
				else{
					Y[{x[i]-1,y[i]-1}]=A;
				}
				if(Y.count({x[i]-1,y[i]+1})){
					int B=Y[{x[i]-1,y[i]+1}];
					add_edge(A,B,x[i]-1,y[i]+1);
					Y.erase({x[i]-1,y[i]+1});
				}
				else{
					Y[{x[i]-1,y[i]+1}]=A;
				}
			}
		}
		if(X.count({x[i],y[i]-2})){
			int j=X[{x[i],y[i]-2}];
			if(add(i,j)){
				u.pb(i);v.pb(j);
				a.pb(-1);b.pb(-1);
				int A=u.size()-1;
				if(Y.count({x[i]-1,y[i]-1})){
					int B=Y[{x[i]-1,y[i]-1}];
					add_edge(A,B,x[i]-1,y[i]-1);
					Y.erase({x[i]-1,y[i]-1});
				}
				else{
					Y[{x[i]-1,y[i]-1}]=A;
				}
				if(Y.count({x[i]+1,y[i]-1})){
					int B=Y[{x[i]+1,y[i]-1}];
					add_edge(A,B,x[i]+1,y[i]-1);
					Y.erase({x[i]+1,y[i]-1});
				}
				else{
					Y[{x[i]+1,y[i]+1}]=A;
				}
			}
		}
	}
	if(sz[f(0)]<n) return 0;
	int m=u.size();
	vector<int> used(m);
	function<void(int)> dfs=[&](int x){
		used[x]=1;
		for(auto [it,A,B]:g[x]){
			if(used[it]) continue;
			a[it]=A;
			b[it]=B;
			dfs(it);
		}
	};
	for(auto [it,A]: Y){
		if(used[A]) continue;
		a[A]=it.fr;
		b[A]=it.sc;
		dfs(A);
	}
	for(int i=0;i<m;i++){
		if(used[i]) continue;
		a[i]=g[i].back()[1];
		b[i]=g[i].back()[2];
		g[i].pop_back();
		dfs(i);
	}
	build(u,v,a,b);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5736 KB Output is correct
5 Correct 3 ms 5800 KB Output is correct
6 Correct 3 ms 5808 KB Output is correct
7 Correct 4 ms 5804 KB Output is correct
8 Correct 4 ms 5804 KB Output is correct
9 Correct 307 ms 30092 KB Output is correct
10 Correct 13 ms 8372 KB Output is correct
11 Correct 69 ms 18740 KB Output is correct
12 Correct 19 ms 9604 KB Output is correct
13 Correct 51 ms 14804 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 5 ms 6100 KB Output is correct
16 Correct 237 ms 30160 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5736 KB Output is correct
5 Correct 3 ms 5800 KB Output is correct
6 Correct 3 ms 5808 KB Output is correct
7 Correct 4 ms 5804 KB Output is correct
8 Correct 4 ms 5804 KB Output is correct
9 Correct 307 ms 30092 KB Output is correct
10 Correct 13 ms 8372 KB Output is correct
11 Correct 69 ms 18740 KB Output is correct
12 Correct 19 ms 9604 KB Output is correct
13 Correct 51 ms 14804 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 5 ms 6100 KB Output is correct
16 Correct 237 ms 30160 KB Output is correct
17 Incorrect 3 ms 5716 KB Tree (a[1], b[1]) = (5, 5) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(4, 2)
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5736 KB Output is correct
5 Correct 3 ms 5800 KB Output is correct
6 Correct 3 ms 5808 KB Output is correct
7 Correct 4 ms 5804 KB Output is correct
8 Correct 4 ms 5804 KB Output is correct
9 Correct 307 ms 30092 KB Output is correct
10 Correct 13 ms 8372 KB Output is correct
11 Correct 69 ms 18740 KB Output is correct
12 Correct 19 ms 9604 KB Output is correct
13 Correct 51 ms 14804 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 5 ms 6100 KB Output is correct
16 Correct 237 ms 30160 KB Output is correct
17 Incorrect 3 ms 5716 KB Tree (a[1], b[1]) = (5, 5) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(4, 2)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5736 KB Output is correct
5 Correct 3 ms 5800 KB Output is correct
6 Correct 3 ms 5808 KB Output is correct
7 Correct 4 ms 5804 KB Output is correct
8 Correct 4 ms 5804 KB Output is correct
9 Correct 307 ms 30092 KB Output is correct
10 Correct 13 ms 8372 KB Output is correct
11 Correct 69 ms 18740 KB Output is correct
12 Correct 19 ms 9604 KB Output is correct
13 Correct 51 ms 14804 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 5 ms 6100 KB Output is correct
16 Correct 237 ms 30160 KB Output is correct
17 Correct 3 ms 5716 KB Output is correct
18 Correct 3 ms 5796 KB Output is correct
19 Correct 3 ms 5716 KB Output is correct
20 Correct 578 ms 47376 KB Output is correct
21 Incorrect 697 ms 45636 KB Tree (a[0], b[0]) = (56859, 56865) is not adjacent to edge between u[0]=0 @(56858, 56864) and v[0]=178618 @(56858, 56862)
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5736 KB Output is correct
5 Correct 3 ms 5800 KB Output is correct
6 Correct 3 ms 5808 KB Output is correct
7 Correct 4 ms 5804 KB Output is correct
8 Correct 4 ms 5804 KB Output is correct
9 Correct 307 ms 30092 KB Output is correct
10 Correct 13 ms 8372 KB Output is correct
11 Correct 69 ms 18740 KB Output is correct
12 Correct 19 ms 9604 KB Output is correct
13 Correct 51 ms 14804 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 5 ms 6100 KB Output is correct
16 Correct 237 ms 30160 KB Output is correct
17 Correct 690 ms 57228 KB Output is correct
18 Incorrect 674 ms 57268 KB Tree (a[40134], b[40134]) = (50003, 50005) is not adjacent to edge between u[40134]=40135 @(50002, 50004) and v[40134]=183490 @(50002, 50002)
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5716 KB Output is correct
4 Correct 3 ms 5736 KB Output is correct
5 Correct 3 ms 5800 KB Output is correct
6 Correct 3 ms 5808 KB Output is correct
7 Correct 4 ms 5804 KB Output is correct
8 Correct 4 ms 5804 KB Output is correct
9 Correct 307 ms 30092 KB Output is correct
10 Correct 13 ms 8372 KB Output is correct
11 Correct 69 ms 18740 KB Output is correct
12 Correct 19 ms 9604 KB Output is correct
13 Correct 51 ms 14804 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 5 ms 6100 KB Output is correct
16 Correct 237 ms 30160 KB Output is correct
17 Incorrect 3 ms 5716 KB Tree (a[1], b[1]) = (5, 5) is not adjacent to edge between u[1]=0 @(4, 4) and v[1]=2 @(4, 2)
18 Halted 0 ms 0 KB -