oj.uz

Submission #622464

# Submission time Handle Problem Language Result Execution time Memory
622464 2022-08-04T09:58:46 Z Koosha_mv Fountain Parks (IOI21_parks) C++17
5 / 100
 1238 ms 99528 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=2e5+99;

int n,a[N],b[N],f[N];
queue<pair<int,int>> q;
map<int,int> mark[N];
map<pair<int,int>,vector<pair<int,int>>> sq;
map<pair<int,int>,pair<int,int>> tn;

int getpar(int u){
	if(f[u]<0) return u;
	return f[u]=getpar(f[u]);
}
int merge(int u,int v){
	u=getpar(u),v=getpar(v);
	if(u==v) return 0;
	if(f[u]>f[v]) swap(u,v);
	f[u]+=f[v];
	f[v]=u;
	return 1;
}
void del(int x,int y,pair<int,int> p){
	f(i,0,sz(sq[mp(x,y)])){
		if(sq[mp(x,y)][i]==p){
			sq[mp(x,y)].erase(sq[mp(x,y)].begin()+i);
			break ;
		}
	}
	if(sz(sq[mp(x,y)])==1){
		tn[sq[mp(x,y)][0]]=mp(x,y);
		q.push(sq[mp(x,y)][0]);
	}
}
int construct_roads(vector<int> _a,vector<int> _b) {
	fill(f,f+N,-1);
	f(i,0,sz(_a)) a[i+1]=_a[i];
	f(i,0,sz(_b)) b[i+1]=_b[i];
	n=_a.size();
	f(i,1,n+1){
		mark[a[i]][b[i]]=i;
	}
	f(i,1,n+1){
		if(mark[a[i]+2].count(b[i])){
			int j=mark[a[i]+2][b[i]];
			sq[{a[i]+1,b[i]+1}].pb({i,j});
			sq[{a[i]+1,b[i]-1}].pb({i,j});
		}
		if(mark[a[i]].count(b[i]+2)){
			int j=mark[a[i]][b[i]+2];
			sq[{a[i]+1,b[i]+1}].pb({i,j});
			sq[{a[i]-1,b[i]+1}].pb({i,j});	
		}
	}
	for(auto [p,v] : sq){
		if(v.size()==1){
			tn[v[0]]=p;
			q.push(v[0]);
		}
	}
	while(q.size()){
		int u=q.front().F,v=q.front().S;
		q.pop();
		if(a[u]+2==a[v]){
			del(a[u]+1,a[v]+1,mp(u,v));
			del(a[u]+1,a[v]-1,mp(u,v));
		}
		else{
			del(a[u]+1,a[v]+1,mp(u,v));
			del(a[u]-1,a[v]+1,mp(u,v));
		}
	}
	vector<int> U,V,A,B;
	f(i,1,n+1){
		if(mark[a[i]+2].count(b[i])){
			int j=mark[a[i]+2][b[i]];
			if(merge(i,j)){
				U.pb(i-1);
				V.pb(j-1);
				A.pb(tn[mp(i,j)].F);
				B.pb(tn[mp(i,j)].S);
				if(tn.count(mp(i,j))==0){
					assert(0);
				}
			}
		}
		if(mark[a[i]].count(b[i]+2)){
			int j=mark[a[i]][b[i]+2];
			if(merge(i,j)){
				U.pb(i-1);
				V.pb(j-1);
				A.pb(tn[mp(i,j)].F);
				B.pb(tn[mp(i,j)].S);
				if(tn.count(mp(i,j))==0){
					assert(0);
				}
			}	
		}
	}
	if(f[getpar(1)]!=-n) return 0;
	/*cout<<endl;
	cout<<U.size()<<endl;
	f(i,0,n-1){
		cout<<U[i]<<" "<<V[i]<<" "<<A[i]<<" "<<B[i]<<endl;
	}
	cout<<endl;*/
	build(U,V,A,B);
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 5 ms 10392 KB Output is correct
9 Correct 469 ms 51596 KB Output is correct
10 Correct 30 ms 14804 KB Output is correct
11 Correct 157 ms 32680 KB Output is correct
12 Correct 44 ms 16816 KB Output is correct
13 Correct 133 ms 27284 KB Output is correct
14 Correct 8 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 512 ms 51732 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 5 ms 10392 KB Output is correct
9 Correct 469 ms 51596 KB Output is correct
10 Correct 30 ms 14804 KB Output is correct
11 Correct 157 ms 32680 KB Output is correct
12 Correct 44 ms 16816 KB Output is correct
13 Correct 133 ms 27284 KB Output is correct
14 Correct 8 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 512 ms 51732 KB Output is correct
17 Correct 6 ms 10452 KB Output is correct
18 Correct 5 ms 10452 KB Output is correct
19 Incorrect 6 ms 10472 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 5 ms 10392 KB Output is correct
9 Correct 469 ms 51596 KB Output is correct
10 Correct 30 ms 14804 KB Output is correct
11 Correct 157 ms 32680 KB Output is correct
12 Correct 44 ms 16816 KB Output is correct
13 Correct 133 ms 27284 KB Output is correct
14 Correct 8 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 512 ms 51732 KB Output is correct
17 Correct 6 ms 10452 KB Output is correct
18 Correct 5 ms 10452 KB Output is correct
19 Incorrect 6 ms 10472 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 5 ms 10392 KB Output is correct
9 Correct 469 ms 51596 KB Output is correct
10 Correct 30 ms 14804 KB Output is correct
11 Correct 157 ms 32680 KB Output is correct
12 Correct 44 ms 16816 KB Output is correct
13 Correct 133 ms 27284 KB Output is correct
14 Correct 8 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 512 ms 51732 KB Output is correct
17 Correct 6 ms 10452 KB Output is correct
18 Correct 5 ms 10452 KB Output is correct
19 Correct 6 ms 10452 KB Output is correct
20 Incorrect 541 ms 68328 KB a[0] = 0 is not an odd integer
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 5 ms 10392 KB Output is correct
9 Correct 469 ms 51596 KB Output is correct
10 Correct 30 ms 14804 KB Output is correct
11 Correct 157 ms 32680 KB Output is correct
12 Correct 44 ms 16816 KB Output is correct
13 Correct 133 ms 27284 KB Output is correct
14 Correct 8 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 512 ms 51732 KB Output is correct
17 Correct 1090 ms 99528 KB Output is correct
18 Incorrect 1238 ms 99212 KB a[11866] = 0 is not an odd integer
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10580 KB Output is correct
2 Correct 6 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 6 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10452 KB Output is correct
7 Correct 6 ms 10452 KB Output is correct
8 Correct 5 ms 10392 KB Output is correct
9 Correct 469 ms 51596 KB Output is correct
10 Correct 30 ms 14804 KB Output is correct
11 Correct 157 ms 32680 KB Output is correct
12 Correct 44 ms 16816 KB Output is correct
13 Correct 133 ms 27284 KB Output is correct
14 Correct 8 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 512 ms 51732 KB Output is correct
17 Correct 6 ms 10452 KB Output is correct
18 Correct 5 ms 10452 KB Output is correct
19 Incorrect 6 ms 10472 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -