oj.uz

Submission #1059752

# Submission time Handle Problem Language Result Execution time Memory
1059752 2024-08-15T07:47:21 Z pcc Fountain Parks (IOI21_parks) C++17
55 / 100
 527 ms 103744 KB 
#include "parks.h"
#include <bits/stdc++.h>
#include <unistd.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

#define pii pair<int,int>
#define fs first
#define sc second
#define _all(T) T.begin(),T.end()

const int mxn = 2e5+10;
int N;
int S;

struct DSU{
	int dsu[mxn];
	DSU(){
		iota(dsu,dsu+mxn,0);
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		dsu[root(a)] = root(b);
	}
};

DSU dsu;

vector<int> ans[4];

void addans(int s,int e,int x,int y){
	dsu.onion(s,e);
	ans[0].push_back(s);
	ans[1].push_back(e);
	ans[2].push_back(x);
	ans[3].push_back(y);
	return;
}

map<pii,int> mp;
vector<pii> edges;
vector<pii> all;

void check(int a,int b){
	if(dsu.root(a) == dsu.root(b))return;
	edges.push_back(pii(a,b));
	dsu.onion(a,b);
	return;
}

vector<int> lef[mxn],rig[mxn*2];
int mx[mxn],my[mxn*2];
int deg[mxn*6];
bitset<mxn> done;

void dfs(int now){
	if(mx[now] != -1)return;
	int tar = -1;
	for(auto nxt:lef[now]){
		if(my[nxt] == -1){
			if(tar == -1)tar = nxt;
			else if(tar != -1&&deg[nxt]>deg[tar])tar = nxt;
		}
	}
	assert(tar != -1);
	mx[now] = tar;
	my[tar] = now;
	for(auto nxt:rig[mx[now]]){
		if(mx[nxt] == -1)dfs(nxt);
	}
	return;
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
	S = clock();
    if (x.size() == 1) {
		build({}, {}, {}, {});
        return 1;
    }
	N = x.size();
	for(int i = 0;i<N;i++){
		pii pos = pii(x[i],y[i]);
		if(mp.find(pii(pos.fs-2,pos.sc)) != mp.end())check(mp[pii(pos.fs-2,pos.sc)],i);
		if(mp.find(pii(pos.fs+2,pos.sc)) != mp.end())check(mp[pii(pos.fs+2,pos.sc)],i);
		if(mp.find(pii(pos.fs,pos.sc-2)) != mp.end())check(mp[pii(pos.fs,pos.sc-2)],i);
		if(mp.find(pii(pos.fs,pos.sc+2)) != mp.end())check(mp[pii(pos.fs,pos.sc+2)],i);
		mp[pos] = i;
	}
	if(edges.size() != N-1)return 0;
	for(int i = 0;i<edges.size();i++){
		auto [s,e] = edges[i];
		if(x[s]>x[e])swap(s,e);
		if(x[s] == x[e]&&y[s]>y[e])swap(s,e);
		if(x[s] == x[e]){
			all.push_back(pii(x[s]-1,(y[s]+y[e])>>1));
			all.push_back(pii(x[s]+1,(y[s]+y[e])>>1));
		}
		else if(y[s] == y[e]){
			all.push_back(pii((x[s]+x[e])>>1,y[s]-1));
			all.push_back(pii((x[s]+x[e])>>1,y[s]+1));
		}
	}
	//cerr<<"EDGES: ";for(auto [s,e]:edges)cerr<<s<<' '<<e<<endl;
	sort(all.begin(),all.end());all.erase(unique(all.begin(),all.end()),all.end());
	for(int i = 0;i<edges.size();i++){
		auto [s,e] = edges[i];
		if(x[s] == x[e]){
			int p = lower_bound(_all(all),pii(x[s]-1,(y[s]+y[e])>>1))-all.begin();
			rig[p].push_back(i);
			deg[p]++;
			lef[i].push_back(p);
			p = lower_bound(_all(all),pii(x[s]+1,(y[s]+y[e])>>1))-all.begin();
			rig[p].push_back(i);
			deg[p]++;
			lef[i].push_back(p);
		}
		else if(y[s] == y[e]){
			int p = lower_bound(_all(all),pii((x[s]+x[e])>>1,y[s]-1))-all.begin();
			deg[p]++;
			rig[p].push_back(i);
			lef[i].push_back(p);
			p = lower_bound(_all(all),pii((x[s]+x[e])>>1,y[s]+1))-all.begin();
			rig[p].push_back(i);
			deg[p]++;
			lef[i].push_back(p);
		}
	}

	queue<int> q;
	for(int i = 0;i<all.size();i++){
		if(deg[i] == 1)q.push(i);
	}

	memset(mx,-1,sizeof(mx));
	memset(my,-1,sizeof(my));

	while(!q.empty()){
		auto now = q.front();
		q.pop();
		int tar = -1;
		for(auto nxt:rig[now]){
			if(mx[nxt] == -1)tar = nxt;
		}
		if(tar == -1)continue;
		mx[tar] = now;
		my[now] = tar;
		for(auto nxt:lef[tar]){
			deg[nxt]--;
			if(deg[nxt] == 1)q.push(nxt);
		}
	}

	for(int i = 0;i<all.size();i++){
		if(my[i] != -1)continue;
		if(deg[i] == 3){
			int tar = -1;
			vector<int> v;
			map<int,int> mp;
			for(auto &j:rig[i]){
				if(mx[j] != -1)continue;
				auto &[s,e]=edges[j];
				mp[s]++;
				mp[e]++;
				if(x[s]>x[e]||(x[s] == x[e]&&y[s]>y[e]))swap(s,e);
				v.push_back(j);
			}
			pii pos = pii(-1,-1);
			for(auto &j:mp){
				if(j.sc>1){
					if(pos.fs == -1)pos.fs = j.fs;
					else pos.sc = j.fs;
				}
			}
			if(v.size() != 3)exit(0);
			assert(v.size() == 3);
			for(auto &j:v){
				auto now = edges[j];
				if(now.fs == pos.fs&&now.sc == pos.sc)tar = j;
				else if(now.fs == pos.sc&&now.sc == pos.fs)tar = j;
			}
			if(tar == -1)exit(0);
			assert(tar != -1);
			mx[tar] = i;
			my[i] = tar;
			for(auto &j:rig[i]){
				if(mx[j] == -1)dfs(j);
			}
		}
	}

	for(int i = 0;i<edges.size();i++){
		if(mx[i] != -1)continue;
		dfs(i);
	}
	

	for(int i = 0;i<edges.size();i++){
		if(mx[i] == -1)return 0;
		int tar = mx[i];
		addans(edges[i].fs,edges[i].sc,all[tar].fs,all[tar].sc);
	}

	build(ans[0],ans[1],ans[2],ans[3]);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:93:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   93 |  if(edges.size() != N-1)return 0;
      |     ~~~~~~~~~~~~~^~~~~~
parks.cpp:94:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:109:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:134:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
parks.cpp:157:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
parks.cpp:195:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:201:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15104 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 189 ms 45260 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 75 ms 33172 KB Output is correct
12 Correct 22 ms 21968 KB Output is correct
13 Correct 31 ms 19268 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 197 ms 45376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15104 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 189 ms 45260 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 75 ms 33172 KB Output is correct
12 Correct 22 ms 21968 KB Output is correct
13 Correct 31 ms 19268 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 197 ms 45376 KB Output is correct
17 Correct 7 ms 17496 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 7 ms 17604 KB Output is correct
20 Correct 10 ms 17500 KB Output is correct
21 Correct 8 ms 15196 KB Output is correct
22 Correct 10 ms 17672 KB Output is correct
23 Correct 500 ms 65820 KB Output is correct
24 Correct 7 ms 17500 KB Output is correct
25 Correct 14 ms 17752 KB Output is correct
26 Correct 8 ms 15452 KB Output is correct
27 Correct 8 ms 15452 KB Output is correct
28 Correct 182 ms 36256 KB Output is correct
29 Correct 278 ms 45968 KB Output is correct
30 Correct 362 ms 55412 KB Output is correct
31 Correct 454 ms 64768 KB Output is correct
32 Correct 9 ms 17496 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 6 ms 15196 KB Output is correct
36 Correct 6 ms 15196 KB Output is correct
37 Correct 7 ms 17500 KB Output is correct
38 Correct 9 ms 17500 KB Output is correct
39 Correct 7 ms 17500 KB Output is correct
40 Correct 8 ms 17500 KB Output is correct
41 Correct 7 ms 15196 KB Output is correct
42 Correct 6 ms 17544 KB Output is correct
43 Correct 7 ms 15452 KB Output is correct
44 Correct 8 ms 15448 KB Output is correct
45 Correct 193 ms 42540 KB Output is correct
46 Correct 307 ms 53864 KB Output is correct
47 Correct 321 ms 53944 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15104 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 189 ms 45260 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 75 ms 33172 KB Output is correct
12 Correct 22 ms 21968 KB Output is correct
13 Correct 31 ms 19268 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 197 ms 45376 KB Output is correct
17 Correct 7 ms 17496 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 7 ms 17604 KB Output is correct
20 Correct 10 ms 17500 KB Output is correct
21 Correct 8 ms 15196 KB Output is correct
22 Correct 10 ms 17672 KB Output is correct
23 Correct 500 ms 65820 KB Output is correct
24 Correct 7 ms 17500 KB Output is correct
25 Correct 14 ms 17752 KB Output is correct
26 Correct 8 ms 15452 KB Output is correct
27 Correct 8 ms 15452 KB Output is correct
28 Correct 182 ms 36256 KB Output is correct
29 Correct 278 ms 45968 KB Output is correct
30 Correct 362 ms 55412 KB Output is correct
31 Correct 454 ms 64768 KB Output is correct
32 Correct 9 ms 17496 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 6 ms 15196 KB Output is correct
36 Correct 6 ms 15196 KB Output is correct
37 Correct 7 ms 17500 KB Output is correct
38 Correct 9 ms 17500 KB Output is correct
39 Correct 7 ms 17500 KB Output is correct
40 Correct 8 ms 17500 KB Output is correct
41 Correct 7 ms 15196 KB Output is correct
42 Correct 6 ms 17544 KB Output is correct
43 Correct 7 ms 15452 KB Output is correct
44 Correct 8 ms 15448 KB Output is correct
45 Correct 193 ms 42540 KB Output is correct
46 Correct 307 ms 53864 KB Output is correct
47 Correct 321 ms 53944 KB Output is correct
48 Correct 10 ms 17496 KB Output is correct
49 Correct 7 ms 17500 KB Output is correct
50 Correct 6 ms 17504 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 7 ms 17500 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 17500 KB Output is correct
55 Runtime error 422 ms 103744 KB Execution killed with signal 6
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15104 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 189 ms 45260 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 75 ms 33172 KB Output is correct
12 Correct 22 ms 21968 KB Output is correct
13 Correct 31 ms 19268 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 197 ms 45376 KB Output is correct
17 Correct 6 ms 17500 KB Output is correct
18 Correct 6 ms 17500 KB Output is correct
19 Correct 6 ms 15196 KB Output is correct
20 Correct 448 ms 64980 KB Output is correct
21 Correct 416 ms 64796 KB Output is correct
22 Correct 427 ms 64708 KB Output is correct
23 Correct 358 ms 64000 KB Output is correct
24 Correct 200 ms 30908 KB Output is correct
25 Correct 258 ms 32448 KB Output is correct
26 Correct 222 ms 32492 KB Output is correct
27 Correct 484 ms 71744 KB Output is correct
28 Correct 517 ms 71616 KB Output is correct
29 Correct 505 ms 72380 KB Output is correct
30 Correct 497 ms 72804 KB Output is correct
31 Correct 10 ms 17496 KB Output is correct
32 Correct 33 ms 21388 KB Output is correct
33 Correct 86 ms 23892 KB Output is correct
34 Correct 443 ms 66596 KB Output is correct
35 Correct 17 ms 16220 KB Output is correct
36 Correct 55 ms 19912 KB Output is correct
37 Correct 116 ms 24648 KB Output is correct
38 Correct 168 ms 38124 KB Output is correct
39 Correct 250 ms 45284 KB Output is correct
40 Correct 350 ms 53620 KB Output is correct
41 Correct 428 ms 60932 KB Output is correct
42 Correct 527 ms 67900 KB Output is correct
43 Correct 7 ms 17500 KB Output is correct
44 Correct 7 ms 17592 KB Output is correct
45 Correct 7 ms 17500 KB Output is correct
46 Correct 6 ms 15196 KB Output is correct
47 Correct 6 ms 15196 KB Output is correct
48 Correct 6 ms 17500 KB Output is correct
49 Correct 7 ms 17500 KB Output is correct
50 Correct 7 ms 17500 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 9 ms 15196 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 15452 KB Output is correct
55 Correct 7 ms 15452 KB Output is correct
56 Correct 204 ms 43276 KB Output is correct
57 Correct 304 ms 54736 KB Output is correct
58 Correct 299 ms 55244 KB Output is correct
59 Correct 6 ms 15192 KB Output is correct
60 Correct 7 ms 17596 KB Output is correct
61 Correct 6 ms 15196 KB Output is correct
62 Correct 404 ms 73248 KB Output is correct
63 Correct 421 ms 73244 KB Output is correct
64 Correct 410 ms 73044 KB Output is correct
65 Correct 8 ms 15448 KB Output is correct
66 Correct 11 ms 15972 KB Output is correct
67 Correct 205 ms 43312 KB Output is correct
68 Correct 334 ms 56240 KB Output is correct
69 Correct 475 ms 69476 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15104 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 189 ms 45260 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 75 ms 33172 KB Output is correct
12 Correct 22 ms 21968 KB Output is correct
13 Correct 31 ms 19268 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 197 ms 45376 KB Output is correct
17 Correct 417 ms 74012 KB Output is correct
18 Correct 421 ms 74336 KB Output is correct
19 Correct 448 ms 66708 KB Output is correct
20 Correct 492 ms 66124 KB Output is correct
21 Correct 435 ms 64496 KB Output is correct
22 Correct 8 ms 17496 KB Output is correct
23 Correct 64 ms 26004 KB Output is correct
24 Correct 24 ms 17112 KB Output is correct
25 Correct 83 ms 22472 KB Output is correct
26 Correct 147 ms 27076 KB Output is correct
27 Correct 222 ms 43964 KB Output is correct
28 Correct 294 ms 50356 KB Output is correct
29 Correct 373 ms 57252 KB Output is correct
30 Correct 428 ms 62952 KB Output is correct
31 Correct 508 ms 70168 KB Output is correct
32 Correct 449 ms 69412 KB Output is correct
33 Correct 402 ms 73164 KB Output is correct
34 Correct 9 ms 15708 KB Output is correct
35 Correct 12 ms 16048 KB Output is correct
36 Correct 211 ms 42952 KB Output is correct
37 Correct 327 ms 56384 KB Output is correct
38 Correct 457 ms 68196 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15192 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 7 ms 15196 KB Output is correct
4 Correct 8 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 6 ms 15104 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 189 ms 45260 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 75 ms 33172 KB Output is correct
12 Correct 22 ms 21968 KB Output is correct
13 Correct 31 ms 19268 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 197 ms 45376 KB Output is correct
17 Correct 7 ms 17496 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 7 ms 17604 KB Output is correct
20 Correct 10 ms 17500 KB Output is correct
21 Correct 8 ms 15196 KB Output is correct
22 Correct 10 ms 17672 KB Output is correct
23 Correct 500 ms 65820 KB Output is correct
24 Correct 7 ms 17500 KB Output is correct
25 Correct 14 ms 17752 KB Output is correct
26 Correct 8 ms 15452 KB Output is correct
27 Correct 8 ms 15452 KB Output is correct
28 Correct 182 ms 36256 KB Output is correct
29 Correct 278 ms 45968 KB Output is correct
30 Correct 362 ms 55412 KB Output is correct
31 Correct 454 ms 64768 KB Output is correct
32 Correct 9 ms 17496 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 6 ms 15196 KB Output is correct
36 Correct 6 ms 15196 KB Output is correct
37 Correct 7 ms 17500 KB Output is correct
38 Correct 9 ms 17500 KB Output is correct
39 Correct 7 ms 17500 KB Output is correct
40 Correct 8 ms 17500 KB Output is correct
41 Correct 7 ms 15196 KB Output is correct
42 Correct 6 ms 17544 KB Output is correct
43 Correct 7 ms 15452 KB Output is correct
44 Correct 8 ms 15448 KB Output is correct
45 Correct 193 ms 42540 KB Output is correct
46 Correct 307 ms 53864 KB Output is correct
47 Correct 321 ms 53944 KB Output is correct
48 Correct 10 ms 17496 KB Output is correct
49 Correct 7 ms 17500 KB Output is correct
50 Correct 6 ms 17504 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 7 ms 17500 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 17500 KB Output is correct
55 Runtime error 422 ms 103744 KB Execution killed with signal 6
56 Halted 0 ms 0 KB -