oj.uz

Submission #622455

# Submission time Handle Problem Language Result Execution time Memory
622455 2022-08-04T09:49:53 Z Koosha_mv Fountain Parks (IOI21_parks) C++17
5 / 100
 1082 ms 101384 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));
		}
	}
	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 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10472 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10472 KB Output is correct
7 Correct 5 ms 10464 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 465 ms 52512 KB Output is correct
10 Correct 23 ms 14804 KB Output is correct
11 Correct 120 ms 33044 KB Output is correct
12 Correct 33 ms 17016 KB Output is correct
13 Correct 87 ms 27636 KB Output is correct
14 Correct 7 ms 10864 KB Output is correct
15 Correct 9 ms 11148 KB Output is correct
16 Correct 454 ms 52496 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 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10472 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10472 KB Output is correct
7 Correct 5 ms 10464 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 465 ms 52512 KB Output is correct
10 Correct 23 ms 14804 KB Output is correct
11 Correct 120 ms 33044 KB Output is correct
12 Correct 33 ms 17016 KB Output is correct
13 Correct 87 ms 27636 KB Output is correct
14 Correct 7 ms 10864 KB Output is correct
15 Correct 9 ms 11148 KB Output is correct
16 Correct 454 ms 52496 KB Output is correct
17 Correct 5 ms 10392 KB Output is correct
18 Correct 6 ms 10396 KB Output is correct
19 Incorrect 5 ms 10476 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 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10472 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10472 KB Output is correct
7 Correct 5 ms 10464 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 465 ms 52512 KB Output is correct
10 Correct 23 ms 14804 KB Output is correct
11 Correct 120 ms 33044 KB Output is correct
12 Correct 33 ms 17016 KB Output is correct
13 Correct 87 ms 27636 KB Output is correct
14 Correct 7 ms 10864 KB Output is correct
15 Correct 9 ms 11148 KB Output is correct
16 Correct 454 ms 52496 KB Output is correct
17 Correct 5 ms 10392 KB Output is correct
18 Correct 6 ms 10396 KB Output is correct
19 Incorrect 5 ms 10476 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 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10472 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10472 KB Output is correct
7 Correct 5 ms 10464 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 465 ms 52512 KB Output is correct
10 Correct 23 ms 14804 KB Output is correct
11 Correct 120 ms 33044 KB Output is correct
12 Correct 33 ms 17016 KB Output is correct
13 Correct 87 ms 27636 KB Output is correct
14 Correct 7 ms 10864 KB Output is correct
15 Correct 9 ms 11148 KB Output is correct
16 Correct 454 ms 52496 KB Output is correct
17 Correct 5 ms 10452 KB Output is correct
18 Correct 6 ms 10452 KB Output is correct
19 Correct 6 ms 10452 KB Output is correct
20 Incorrect 513 ms 70968 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 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10472 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10472 KB Output is correct
7 Correct 5 ms 10464 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 465 ms 52512 KB Output is correct
10 Correct 23 ms 14804 KB Output is correct
11 Correct 120 ms 33044 KB Output is correct
12 Correct 33 ms 17016 KB Output is correct
13 Correct 87 ms 27636 KB Output is correct
14 Correct 7 ms 10864 KB Output is correct
15 Correct 9 ms 11148 KB Output is correct
16 Correct 454 ms 52496 KB Output is correct
17 Correct 1032 ms 101384 KB Output is correct
18 Incorrect 1082 ms 101096 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 6 ms 10452 KB Output is correct
3 Correct 5 ms 10452 KB Output is correct
4 Correct 6 ms 10472 KB Output is correct
5 Correct 5 ms 10452 KB Output is correct
6 Correct 5 ms 10472 KB Output is correct
7 Correct 5 ms 10464 KB Output is correct
8 Correct 5 ms 10452 KB Output is correct
9 Correct 465 ms 52512 KB Output is correct
10 Correct 23 ms 14804 KB Output is correct
11 Correct 120 ms 33044 KB Output is correct
12 Correct 33 ms 17016 KB Output is correct
13 Correct 87 ms 27636 KB Output is correct
14 Correct 7 ms 10864 KB Output is correct
15 Correct 9 ms 11148 KB Output is correct
16 Correct 454 ms 52496 KB Output is correct
17 Correct 5 ms 10392 KB Output is correct
18 Correct 6 ms 10396 KB Output is correct
19 Incorrect 5 ms 10476 KB a[0] = 0 is not an odd integer
20 Halted 0 ms 0 KB -