oj.uz

Submission #1039681

# Submission time Handle Problem Language Result Execution time Memory
1039681 2024-07-31T07:30:28 Z Alihan_8 Fountain Parks (IOI21_parks) C++17
5 / 100
 691 ms 160064 KB 
#include "parks.h"

#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//#define int long long

using i64 = long long;

template <class F, class _S>
bool chmin(F &u, const _S &v){
    bool flag = false;
    if ( u > v ){
        u = v; flag |= true;
    }
    return flag;
}

template <class F, class _S>
bool chmax(F &u, const _S &v){
    bool flag = false;
    if ( u < v ){
        u = v; flag |= true;
    }
    return flag;
}

struct Dsu{
	vector <int> fa;
	
	int n;
	
	Dsu(int n) : n(n) {
		fa.resize(n);
		iota(all(fa), 0);
	}
	
	int get(int u){
		return u ^ fa[u] ? fa[u] = get(fa[u]) : u;
	}
	
	bool merge(int u, int v){
		u = get(u), v = get(v);
		
		if ( u == v ) return false;
		
		fa[v] = u;
		
		return true;
	}
	
};

int dx[] = {2, -2, 0, 0};
int dy[] = {0, 0, -2, 2};

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int n = x.size();
    
    map <int,map<int,int>> id;
    
    for ( int i = 0; i < n; i++ ){
		id[x[i]][y[i]] = i;
	}
	
	vector <ar<int,2>> e;
	
	Dsu ds(n);
	
	map <ar<int,2>,int> mp;
	
	for ( int i = 0; i < n; i++ ){
		for ( int j = 0; j < 4; j++ ){
			int u = x[i] + dx[j], v = y[i] + dy[j];
			
			if ( !id[u].count(v) ) continue;
			
			if ( ds.merge(id[u][v], i) ){
				e.pb({id[u][v], i});
				
				mp[{id[u][v], i}] = mp[{i, id[u][v]}] = (int)e.size() - 1;
			}
		}
	}
	
	if ( (int)e.size() != n - 1 ){
		return 0;
	}
	
	//~ for ( int i = 0; i + 1 < n; i++ ){
		//~ cout << e[i][0] << ' ' << e[i][1] << " " << i << ln;
	//~ } cout << ln;
	
	vector <vector<int>> adj(n * 2), rev(n * 2);
	
	auto add = [&](int u, int v){
		//~ cout << u << " " << v << ln;
		
		adj[u].pb(v);
		rev[v].pb(u);
	};
	
	for ( int i = 0; i < n - 1; i++ ){
		auto [u, v] = e[i];
		
		if ( x[u] == x[v] ){ // vertical
			if ( y[u] > y[v] ) swap(u, v);
			
			{ // 0
				int a = -1, b = -1;
				
				if ( id[x[u] + 2].count(y[u]) ){
					int j = id[x[u] + 2][y[u]]; a = j;
					
					if ( mp.count({u, j}) ){
						int k = mp[{u, j}];
						
						add(i, k);
					}
				}
				
				if ( id[x[u] + 2].count(y[v]) ){
					int j = id[x[u] + 2][y[v]]; b = j;
					
					if ( mp.count({j, v}) ){
						int k = mp[{j, v}];
						
						add(i, k + n);
					}
				}
				
				if ( mp.count({a, b}) ){
					add(i, mp[{a, b}]);
				}
			}
			
			{
				int a = -1, b = -1;
					
				if ( id[x[u] - 2].count(y[u]) ){
					int j = id[x[u] - 2][y[u]]; a = j;
					
					if ( mp.count({u, j}) ){
						int k = mp[{u, j}];
						
						add(i + n, k);
					}
				}
				
				if ( id[x[u] - 2].count(y[v]) ){
					int j = id[x[u] - 2][y[v]]; b = j;
					
					if ( mp.count({j, v}) ){
						int k = mp[{j, v}];
						
						add(i + n, k + n);
					}
				}
				
				if ( mp.count({a, b}) ){
					add(i + n, mp[{a, b}] + n);
				}
			}
		} else{ // horizontal
			if ( x[u] > x[v] ) swap(u, v);
			
			{ // 0
				int a = -1, b = -1;
					
				if ( id[x[u]].count(y[u] - 2) ){
					int j = id[x[u]][y[u] - 2]; a = j;
					
					if ( mp.count({u, j}) ){
						int k = mp[{u, j}];
						
						add(i, k + n);
					}
				}
				
				if ( id[x[v]].count(y[v] - 2) ){
					int j = id[x[v]][y[v] - 2]; b = j;
					
					if ( mp.count({j, v}) ){
						int k = mp[{j, v}];
						
						add(i, k);
					}
				}
				
				if ( mp.count({a, b}) ){
					add(i, mp[{a, b}]);
				}
			}
			{ // 1
				int a = -1, b = -1;
					
				if ( id[x[u]].count(y[u] + 2) ){
					int j = id[x[u]][y[u] + 2]; a = j;
					
					if ( mp.count({u, j}) ){
						int k = mp[{u, j}];
						
						add(i + n, k + n);
					}
				}
				
				if ( id[x[v]].count(y[v] + 2) ){
					int j = id[x[v]][y[v] + 2]; b = j;
					
					if ( mp.count({j, v}) ){
						int k = mp[{j, v}];
						
						add(i + n, k);
					}
				}
				
				if ( mp.count({a, b}) ){
					add(i + n, mp[{a, b}]);
				}
			}
		}
	}
	
	vector <int> ord, us(n * 2);
	
	auto dfs = [&](auto dfs, int u) -> void{
		if ( us[u] ) return;
		
		us[u] = true;
		
		for ( auto &v: adj[u] ){
			dfs(dfs, v);
		}
		
		ord.pb(u);
	};
	
	for ( int i = 0; i < n * 2; i++ ){
		dfs(dfs, i);
	}
	
	reverse(all(ord));
	
	vector <int> c(n * 2, -1);
	
	int ct = 0;
	
	auto trav = [&](auto trav, int u) -> void{
		if ( c[u] != -1 ) return;
		
		c[u] = ct;
		
		for ( auto &v: rev[u] ){
			trav(trav, v);
		}
	};
	
	for ( auto &u: ord ){
		if ( c[u] != -1 ) continue;
		
		trav(trav, u);
		
		ct++;
	}
	
	vector <int> t(n - 1);
	
	for ( int i = 0; i + 1 < n; i++ ){
		if ( c[i] == c[i + n] ){
			return 0;
		}
		
		t[i] = (c[i] > c[i + n]);
	}
	
	vector <int> U, V, A, B;
	
	set <pair<int,int>> st;
	
	for ( int i = 0; i + 1 < n; i++ ){
		auto [u, v] = e[i];
		
		U.pb(u), V.pb(v);
		
		if ( x[u] == x[v] ){
			if ( y[u] > y[v] ) swap(u, v);
			
			A.pb(x[u] + (t[i] ? -1 : 1));
			B.pb(y[u] + 1);
		} else{
			if ( x[u] > x[v] ) swap(u, v);
			
			A.pb(x[u] + 1);
			B.pb(y[u] + (t[i] ? 1 : -1));
		}
		
		assert(!st.count({A.back(), B.back()}));
		
		st.insert({A.back(), B.back()});
	}
	
	build(U, V, A, B);
	
	return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 266 ms 42052 KB Output is correct
10 Correct 17 ms 4444 KB Output is correct
11 Correct 84 ms 22628 KB Output is correct
12 Correct 21 ms 6492 KB Output is correct
13 Correct 40 ms 9160 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 260 ms 41988 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 266 ms 42052 KB Output is correct
10 Correct 17 ms 4444 KB Output is correct
11 Correct 84 ms 22628 KB Output is correct
12 Correct 21 ms 6492 KB Output is correct
13 Correct 40 ms 9160 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 260 ms 41988 KB Output is correct
17 Runtime error 1 ms 344 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 266 ms 42052 KB Output is correct
10 Correct 17 ms 4444 KB Output is correct
11 Correct 84 ms 22628 KB Output is correct
12 Correct 21 ms 6492 KB Output is correct
13 Correct 40 ms 9160 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 260 ms 41988 KB Output is correct
17 Runtime error 1 ms 344 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 266 ms 42052 KB Output is correct
10 Correct 17 ms 4444 KB Output is correct
11 Correct 84 ms 22628 KB Output is correct
12 Correct 21 ms 6492 KB Output is correct
13 Correct 40 ms 9160 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 260 ms 41988 KB Output is correct
17 Runtime error 1 ms 348 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 266 ms 42052 KB Output is correct
10 Correct 17 ms 4444 KB Output is correct
11 Correct 84 ms 22628 KB Output is correct
12 Correct 21 ms 6492 KB Output is correct
13 Correct 40 ms 9160 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 260 ms 41988 KB Output is correct
17 Runtime error 691 ms 160064 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 266 ms 42052 KB Output is correct
10 Correct 17 ms 4444 KB Output is correct
11 Correct 84 ms 22628 KB Output is correct
12 Correct 21 ms 6492 KB Output is correct
13 Correct 40 ms 9160 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 260 ms 41988 KB Output is correct
17 Runtime error 1 ms 344 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -