oj.uz

Submission #622459

# Submission time Handle Problem Language Result Execution time Memory
622459 2022-08-04T09:52:53 Z Koosha_mv Fountain Parks (IOI21_parks) C++17
5 / 100
 1166 ms 99592 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(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(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 5 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 5 ms 10400 KB Output is correct
9 Correct 534 ms 51568 KB Output is correct
10 Correct 26 ms 14780 KB Output is correct
11 Correct 157 ms 32620 KB Output is correct
12 Correct 38 ms 16840 KB Output is correct
13 Correct 114 ms 27388 KB Output is correct
14 Correct 7 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 483 ms 51544 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 5 ms 10400 KB Output is correct
9 Correct 534 ms 51568 KB Output is correct
10 Correct 26 ms 14780 KB Output is correct
11 Correct 157 ms 32620 KB Output is correct
12 Correct 38 ms 16840 KB Output is correct
13 Correct 114 ms 27388 KB Output is correct
14 Correct 7 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 483 ms 51544 KB Output is correct
17 Correct 5 ms 10452 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Incorrect 5 ms 10452 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 5 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 5 ms 10400 KB Output is correct
9 Correct 534 ms 51568 KB Output is correct
10 Correct 26 ms 14780 KB Output is correct
11 Correct 157 ms 32620 KB Output is correct
12 Correct 38 ms 16840 KB Output is correct
13 Correct 114 ms 27388 KB Output is correct
14 Correct 7 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 483 ms 51544 KB Output is correct
17 Correct 5 ms 10452 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Incorrect 5 ms 10452 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 5 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 5 ms 10400 KB Output is correct
9 Correct 534 ms 51568 KB Output is correct
10 Correct 26 ms 14780 KB Output is correct
11 Correct 157 ms 32620 KB Output is correct
12 Correct 38 ms 16840 KB Output is correct
13 Correct 114 ms 27388 KB Output is correct
14 Correct 7 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 483 ms 51544 KB Output is correct
17 Correct 5 ms 10452 KB Output is correct
18 Correct 6 ms 10452 KB Output is correct
19 Correct 5 ms 10452 KB Output is correct
20 Incorrect 485 ms 68380 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 5 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 5 ms 10400 KB Output is correct
9 Correct 534 ms 51568 KB Output is correct
10 Correct 26 ms 14780 KB Output is correct
11 Correct 157 ms 32620 KB Output is correct
12 Correct 38 ms 16840 KB Output is correct
13 Correct 114 ms 27388 KB Output is correct
14 Correct 7 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 483 ms 51544 KB Output is correct
17 Correct 1018 ms 99592 KB Output is correct
18 Incorrect 1166 ms 99180 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 5 ms 10452 KB Output is correct
2 Correct 7 ms 10452 KB Output is correct
3 Correct 6 ms 10452 KB Output is correct
4 Correct 7 ms 10452 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 6 ms 10452 KB Output is correct
7 Correct 5 ms 10452 KB Output is correct
8 Correct 5 ms 10400 KB Output is correct
9 Correct 534 ms 51568 KB Output is correct
10 Correct 26 ms 14780 KB Output is correct
11 Correct 157 ms 32620 KB Output is correct
12 Correct 38 ms 16840 KB Output is correct
13 Correct 114 ms 27388 KB Output is correct
14 Correct 7 ms 10836 KB Output is correct
15 Correct 9 ms 11220 KB Output is correct
16 Correct 483 ms 51544 KB Output is correct
17 Correct 5 ms 10452 KB Output is correct
18 Correct 7 ms 10452 KB Output is correct
19 Incorrect 5 ms 10452 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -