oj.uz

Submission #1059747

# Submission time Handle Problem Language Result Execution time Memory
1059747 2024-08-15T07:45:14 Z pcc Fountain Parks (IOI21_parks) C++17
55 / 100
 550 ms 74404 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(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.sc;
				}
			}
			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:194: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]
  194 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:200: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]
  200 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 6 ms 15196 KB Output is correct
4 Correct 7 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15260 KB Output is correct
7 Correct 7 ms 15196 KB Output is correct
8 Correct 6 ms 15080 KB Output is correct
9 Correct 184 ms 45360 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33340 KB Output is correct
12 Correct 23 ms 21980 KB Output is correct
13 Correct 33 ms 19404 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15264 KB Output is correct
16 Correct 185 ms 45336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 6 ms 15196 KB Output is correct
4 Correct 7 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15260 KB Output is correct
7 Correct 7 ms 15196 KB Output is correct
8 Correct 6 ms 15080 KB Output is correct
9 Correct 184 ms 45360 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33340 KB Output is correct
12 Correct 23 ms 21980 KB Output is correct
13 Correct 33 ms 19404 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15264 KB Output is correct
16 Correct 185 ms 45336 KB Output is correct
17 Correct 7 ms 17500 KB Output is correct
18 Correct 8 ms 17616 KB Output is correct
19 Correct 7 ms 17580 KB Output is correct
20 Correct 7 ms 17496 KB Output is correct
21 Correct 6 ms 15196 KB Output is correct
22 Correct 8 ms 17500 KB Output is correct
23 Correct 470 ms 65880 KB Output is correct
24 Correct 7 ms 17496 KB Output is correct
25 Correct 8 ms 17756 KB Output is correct
26 Correct 7 ms 15580 KB Output is correct
27 Correct 9 ms 15628 KB Output is correct
28 Correct 156 ms 36792 KB Output is correct
29 Correct 264 ms 46856 KB Output is correct
30 Correct 357 ms 56312 KB Output is correct
31 Correct 477 ms 65820 KB Output is correct
32 Correct 7 ms 17496 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 7 ms 17552 KB Output is correct
35 Correct 6 ms 15228 KB Output is correct
36 Correct 6 ms 15196 KB Output is correct
37 Correct 7 ms 17500 KB Output is correct
38 Correct 8 ms 17496 KB Output is correct
39 Correct 9 ms 17496 KB Output is correct
40 Correct 7 ms 17500 KB Output is correct
41 Correct 6 ms 15296 KB Output is correct
42 Correct 7 ms 17500 KB Output is correct
43 Correct 7 ms 15448 KB Output is correct
44 Correct 8 ms 15452 KB Output is correct
45 Correct 197 ms 43256 KB Output is correct
46 Correct 309 ms 54732 KB Output is correct
47 Correct 295 ms 54728 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 6 ms 15196 KB Output is correct
4 Correct 7 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15260 KB Output is correct
7 Correct 7 ms 15196 KB Output is correct
8 Correct 6 ms 15080 KB Output is correct
9 Correct 184 ms 45360 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33340 KB Output is correct
12 Correct 23 ms 21980 KB Output is correct
13 Correct 33 ms 19404 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15264 KB Output is correct
16 Correct 185 ms 45336 KB Output is correct
17 Correct 7 ms 17500 KB Output is correct
18 Correct 8 ms 17616 KB Output is correct
19 Correct 7 ms 17580 KB Output is correct
20 Correct 7 ms 17496 KB Output is correct
21 Correct 6 ms 15196 KB Output is correct
22 Correct 8 ms 17500 KB Output is correct
23 Correct 470 ms 65880 KB Output is correct
24 Correct 7 ms 17496 KB Output is correct
25 Correct 8 ms 17756 KB Output is correct
26 Correct 7 ms 15580 KB Output is correct
27 Correct 9 ms 15628 KB Output is correct
28 Correct 156 ms 36792 KB Output is correct
29 Correct 264 ms 46856 KB Output is correct
30 Correct 357 ms 56312 KB Output is correct
31 Correct 477 ms 65820 KB Output is correct
32 Correct 7 ms 17496 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 7 ms 17552 KB Output is correct
35 Correct 6 ms 15228 KB Output is correct
36 Correct 6 ms 15196 KB Output is correct
37 Correct 7 ms 17500 KB Output is correct
38 Correct 8 ms 17496 KB Output is correct
39 Correct 9 ms 17496 KB Output is correct
40 Correct 7 ms 17500 KB Output is correct
41 Correct 6 ms 15296 KB Output is correct
42 Correct 7 ms 17500 KB Output is correct
43 Correct 7 ms 15448 KB Output is correct
44 Correct 8 ms 15452 KB Output is correct
45 Correct 197 ms 43256 KB Output is correct
46 Correct 309 ms 54732 KB Output is correct
47 Correct 295 ms 54728 KB Output is correct
48 Correct 7 ms 17500 KB Output is correct
49 Correct 7 ms 17560 KB Output is correct
50 Correct 7 ms 17500 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 7 ms 17644 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 17500 KB Output is correct
55 Incorrect 390 ms 52716 KB Unexpected end of file - token expected
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 6 ms 15196 KB Output is correct
4 Correct 7 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15260 KB Output is correct
7 Correct 7 ms 15196 KB Output is correct
8 Correct 6 ms 15080 KB Output is correct
9 Correct 184 ms 45360 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33340 KB Output is correct
12 Correct 23 ms 21980 KB Output is correct
13 Correct 33 ms 19404 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15264 KB Output is correct
16 Correct 185 ms 45336 KB Output is correct
17 Correct 7 ms 17500 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 6 ms 15192 KB Output is correct
20 Correct 427 ms 67484 KB Output is correct
21 Correct 443 ms 66912 KB Output is correct
22 Correct 484 ms 66840 KB Output is correct
23 Correct 348 ms 65540 KB Output is correct
24 Correct 192 ms 32340 KB Output is correct
25 Correct 290 ms 33984 KB Output is correct
26 Correct 249 ms 33816 KB Output is correct
27 Correct 501 ms 73180 KB Output is correct
28 Correct 466 ms 73372 KB Output is correct
29 Correct 510 ms 72992 KB Output is correct
30 Correct 493 ms 73300 KB Output is correct
31 Correct 10 ms 17500 KB Output is correct
32 Correct 35 ms 21436 KB Output is correct
33 Correct 88 ms 24280 KB Output is correct
34 Correct 456 ms 67304 KB Output is correct
35 Correct 16 ms 16220 KB Output is correct
36 Correct 60 ms 20196 KB Output is correct
37 Correct 122 ms 25132 KB Output is correct
38 Correct 175 ms 38348 KB Output is correct
39 Correct 253 ms 45532 KB Output is correct
40 Correct 322 ms 54132 KB Output is correct
41 Correct 396 ms 61636 KB Output is correct
42 Correct 501 ms 68640 KB Output is correct
43 Correct 10 ms 17500 KB Output is correct
44 Correct 7 ms 17500 KB Output is correct
45 Correct 10 ms 17500 KB Output is correct
46 Correct 9 ms 15196 KB Output is correct
47 Correct 7 ms 15196 KB Output is correct
48 Correct 8 ms 17500 KB Output is correct
49 Correct 8 ms 17652 KB Output is correct
50 Correct 9 ms 17500 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 6 ms 15316 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 15452 KB Output is correct
55 Correct 11 ms 15528 KB Output is correct
56 Correct 195 ms 43348 KB Output is correct
57 Correct 307 ms 55080 KB Output is correct
58 Correct 306 ms 55236 KB Output is correct
59 Correct 9 ms 15196 KB Output is correct
60 Correct 8 ms 17496 KB Output is correct
61 Correct 6 ms 15196 KB Output is correct
62 Correct 410 ms 73392 KB Output is correct
63 Correct 404 ms 73240 KB Output is correct
64 Correct 420 ms 72896 KB Output is correct
65 Correct 9 ms 15452 KB Output is correct
66 Correct 11 ms 16024 KB Output is correct
67 Correct 204 ms 43276 KB Output is correct
68 Correct 332 ms 56224 KB Output is correct
69 Correct 534 ms 69540 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 6 ms 15196 KB Output is correct
4 Correct 7 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15260 KB Output is correct
7 Correct 7 ms 15196 KB Output is correct
8 Correct 6 ms 15080 KB Output is correct
9 Correct 184 ms 45360 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33340 KB Output is correct
12 Correct 23 ms 21980 KB Output is correct
13 Correct 33 ms 19404 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15264 KB Output is correct
16 Correct 185 ms 45336 KB Output is correct
17 Correct 431 ms 74012 KB Output is correct
18 Correct 449 ms 74404 KB Output is correct
19 Correct 495 ms 66852 KB Output is correct
20 Correct 550 ms 66120 KB Output is correct
21 Correct 465 ms 64416 KB Output is correct
22 Correct 7 ms 17496 KB Output is correct
23 Correct 69 ms 26004 KB Output is correct
24 Correct 31 ms 17112 KB Output is correct
25 Correct 83 ms 22224 KB Output is correct
26 Correct 154 ms 26904 KB Output is correct
27 Correct 227 ms 44032 KB Output is correct
28 Correct 292 ms 50360 KB Output is correct
29 Correct 365 ms 57284 KB Output is correct
30 Correct 460 ms 62768 KB Output is correct
31 Correct 542 ms 70264 KB Output is correct
32 Correct 465 ms 69408 KB Output is correct
33 Correct 399 ms 73272 KB Output is correct
34 Correct 10 ms 15704 KB Output is correct
35 Correct 12 ms 15964 KB Output is correct
36 Correct 200 ms 43104 KB Output is correct
37 Correct 330 ms 56224 KB Output is correct
38 Correct 461 ms 68316 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15196 KB Output is correct
2 Correct 7 ms 17500 KB Output is correct
3 Correct 6 ms 15196 KB Output is correct
4 Correct 7 ms 17500 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15260 KB Output is correct
7 Correct 7 ms 15196 KB Output is correct
8 Correct 6 ms 15080 KB Output is correct
9 Correct 184 ms 45360 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33340 KB Output is correct
12 Correct 23 ms 21980 KB Output is correct
13 Correct 33 ms 19404 KB Output is correct
14 Correct 6 ms 15196 KB Output is correct
15 Correct 7 ms 15264 KB Output is correct
16 Correct 185 ms 45336 KB Output is correct
17 Correct 7 ms 17500 KB Output is correct
18 Correct 8 ms 17616 KB Output is correct
19 Correct 7 ms 17580 KB Output is correct
20 Correct 7 ms 17496 KB Output is correct
21 Correct 6 ms 15196 KB Output is correct
22 Correct 8 ms 17500 KB Output is correct
23 Correct 470 ms 65880 KB Output is correct
24 Correct 7 ms 17496 KB Output is correct
25 Correct 8 ms 17756 KB Output is correct
26 Correct 7 ms 15580 KB Output is correct
27 Correct 9 ms 15628 KB Output is correct
28 Correct 156 ms 36792 KB Output is correct
29 Correct 264 ms 46856 KB Output is correct
30 Correct 357 ms 56312 KB Output is correct
31 Correct 477 ms 65820 KB Output is correct
32 Correct 7 ms 17496 KB Output is correct
33 Correct 7 ms 17500 KB Output is correct
34 Correct 7 ms 17552 KB Output is correct
35 Correct 6 ms 15228 KB Output is correct
36 Correct 6 ms 15196 KB Output is correct
37 Correct 7 ms 17500 KB Output is correct
38 Correct 8 ms 17496 KB Output is correct
39 Correct 9 ms 17496 KB Output is correct
40 Correct 7 ms 17500 KB Output is correct
41 Correct 6 ms 15296 KB Output is correct
42 Correct 7 ms 17500 KB Output is correct
43 Correct 7 ms 15448 KB Output is correct
44 Correct 8 ms 15452 KB Output is correct
45 Correct 197 ms 43256 KB Output is correct
46 Correct 309 ms 54732 KB Output is correct
47 Correct 295 ms 54728 KB Output is correct
48 Correct 7 ms 17500 KB Output is correct
49 Correct 7 ms 17560 KB Output is correct
50 Correct 7 ms 17500 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 7 ms 17644 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 17500 KB Output is correct
55 Incorrect 390 ms 52716 KB Unexpected end of file - token expected
56 Halted 0 ms 0 KB -