oj.uz

Submission #1059690

# Submission time Handle Problem Language Result Execution time Memory
1059690 2024-08-15T07:12:19 Z pcc Fountain Parks (IOI21_parks) C++17
55 / 100
 531 ms 74516 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;
bool has_ans = true;

void dfs(int now){
	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;
		}
	}
	if(tar == -1){
		has_ans = false;
		return;
	}
	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) {
	has_ans = true;
	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<edges.size();i++){
		if(mx[i] != -1)continue;
		dfs(i);
		if(!has_ans)return 0;
	}
	if(!has_ans)return 0;
	

	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:98: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]
   98 |  if(edges.size() != N-1)return 0;
      |     ~~~~~~~~~~~~~^~~~~~
parks.cpp:99: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]
   99 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:114: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]
  114 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:139: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]
  139 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
parks.cpp:162: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]
  162 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:170: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]
  170 |  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 17496 KB Output is correct
3 Correct 6 ms 15080 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 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Correct 7 ms 15196 KB Output is correct
9 Correct 193 ms 45236 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33316 KB Output is correct
12 Correct 23 ms 21972 KB Output is correct
13 Correct 31 ms 19400 KB Output is correct
14 Correct 7 ms 15196 KB Output is correct
15 Correct 7 ms 15312 KB Output is correct
16 Correct 183 ms 45444 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 17496 KB Output is correct
3 Correct 6 ms 15080 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 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Correct 7 ms 15196 KB Output is correct
9 Correct 193 ms 45236 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33316 KB Output is correct
12 Correct 23 ms 21972 KB Output is correct
13 Correct 31 ms 19400 KB Output is correct
14 Correct 7 ms 15196 KB Output is correct
15 Correct 7 ms 15312 KB Output is correct
16 Correct 183 ms 45444 KB Output is correct
17 Correct 8 ms 17496 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 8 ms 17500 KB Output is correct
20 Correct 10 ms 17636 KB Output is correct
21 Correct 6 ms 15196 KB Output is correct
22 Correct 8 ms 17500 KB Output is correct
23 Correct 465 ms 66460 KB Output is correct
24 Correct 9 ms 17752 KB Output is correct
25 Correct 9 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 157 ms 36868 KB Output is correct
29 Correct 250 ms 46996 KB Output is correct
30 Correct 350 ms 56660 KB Output is correct
31 Correct 465 ms 66420 KB Output is correct
32 Correct 7 ms 17496 KB Output is correct
33 Correct 8 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 7 ms 15196 KB Output is correct
36 Correct 7 ms 15196 KB Output is correct
37 Correct 8 ms 17500 KB Output is correct
38 Correct 8 ms 17500 KB Output is correct
39 Correct 8 ms 17652 KB Output is correct
40 Correct 7 ms 17496 KB Output is correct
41 Correct 6 ms 15192 KB Output is correct
42 Correct 7 ms 17652 KB Output is correct
43 Correct 8 ms 15448 KB Output is correct
44 Correct 8 ms 15556 KB Output is correct
45 Correct 201 ms 43260 KB Output is correct
46 Correct 355 ms 55292 KB Output is correct
47 Correct 296 ms 55288 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 17496 KB Output is correct
3 Correct 6 ms 15080 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 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Correct 7 ms 15196 KB Output is correct
9 Correct 193 ms 45236 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33316 KB Output is correct
12 Correct 23 ms 21972 KB Output is correct
13 Correct 31 ms 19400 KB Output is correct
14 Correct 7 ms 15196 KB Output is correct
15 Correct 7 ms 15312 KB Output is correct
16 Correct 183 ms 45444 KB Output is correct
17 Correct 8 ms 17496 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 8 ms 17500 KB Output is correct
20 Correct 10 ms 17636 KB Output is correct
21 Correct 6 ms 15196 KB Output is correct
22 Correct 8 ms 17500 KB Output is correct
23 Correct 465 ms 66460 KB Output is correct
24 Correct 9 ms 17752 KB Output is correct
25 Correct 9 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 157 ms 36868 KB Output is correct
29 Correct 250 ms 46996 KB Output is correct
30 Correct 350 ms 56660 KB Output is correct
31 Correct 465 ms 66420 KB Output is correct
32 Correct 7 ms 17496 KB Output is correct
33 Correct 8 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 7 ms 15196 KB Output is correct
36 Correct 7 ms 15196 KB Output is correct
37 Correct 8 ms 17500 KB Output is correct
38 Correct 8 ms 17500 KB Output is correct
39 Correct 8 ms 17652 KB Output is correct
40 Correct 7 ms 17496 KB Output is correct
41 Correct 6 ms 15192 KB Output is correct
42 Correct 7 ms 17652 KB Output is correct
43 Correct 8 ms 15448 KB Output is correct
44 Correct 8 ms 15556 KB Output is correct
45 Correct 201 ms 43260 KB Output is correct
46 Correct 355 ms 55292 KB Output is correct
47 Correct 296 ms 55288 KB Output is correct
48 Correct 8 ms 17500 KB Output is correct
49 Correct 7 ms 17500 KB Output is correct
50 Correct 7 ms 17496 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 9 ms 17500 KB Output is correct
53 Correct 7 ms 17456 KB Output is correct
54 Correct 7 ms 17500 KB Output is correct
55 Incorrect 399 ms 54668 KB Solution announced impossible, but it is possible.
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 17496 KB Output is correct
3 Correct 6 ms 15080 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 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Correct 7 ms 15196 KB Output is correct
9 Correct 193 ms 45236 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33316 KB Output is correct
12 Correct 23 ms 21972 KB Output is correct
13 Correct 31 ms 19400 KB Output is correct
14 Correct 7 ms 15196 KB Output is correct
15 Correct 7 ms 15312 KB Output is correct
16 Correct 183 ms 45444 KB Output is correct
17 Correct 10 ms 17496 KB Output is correct
18 Correct 8 ms 17496 KB Output is correct
19 Correct 7 ms 15280 KB Output is correct
20 Correct 430 ms 67604 KB Output is correct
21 Correct 459 ms 67104 KB Output is correct
22 Correct 449 ms 67116 KB Output is correct
23 Correct 386 ms 65796 KB Output is correct
24 Correct 189 ms 32596 KB Output is correct
25 Correct 282 ms 33928 KB Output is correct
26 Correct 227 ms 34244 KB Output is correct
27 Correct 454 ms 73244 KB Output is correct
28 Correct 462 ms 73260 KB Output is correct
29 Correct 522 ms 73168 KB Output is correct
30 Correct 481 ms 73252 KB Output is correct
31 Correct 7 ms 17496 KB Output is correct
32 Correct 30 ms 21412 KB Output is correct
33 Correct 80 ms 24404 KB Output is correct
34 Correct 427 ms 67380 KB Output is correct
35 Correct 14 ms 16220 KB Output is correct
36 Correct 57 ms 20172 KB Output is correct
37 Correct 120 ms 25032 KB Output is correct
38 Correct 172 ms 38352 KB Output is correct
39 Correct 243 ms 45536 KB Output is correct
40 Correct 336 ms 54392 KB Output is correct
41 Correct 398 ms 61700 KB Output is correct
42 Correct 515 ms 68892 KB Output is correct
43 Correct 7 ms 17496 KB Output is correct
44 Correct 10 ms 17500 KB Output is correct
45 Correct 8 ms 17572 KB Output is correct
46 Correct 6 ms 15196 KB Output is correct
47 Correct 6 ms 15196 KB Output is correct
48 Correct 7 ms 17624 KB Output is correct
49 Correct 7 ms 17668 KB Output is correct
50 Correct 7 ms 17496 KB Output is correct
51 Correct 8 ms 17500 KB Output is correct
52 Correct 6 ms 15196 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 15384 KB Output is correct
55 Correct 7 ms 15404 KB Output is correct
56 Correct 204 ms 43220 KB Output is correct
57 Correct 305 ms 55244 KB Output is correct
58 Correct 314 ms 55216 KB Output is correct
59 Correct 6 ms 15196 KB Output is correct
60 Correct 7 ms 17552 KB Output is correct
61 Correct 6 ms 15100 KB Output is correct
62 Correct 450 ms 73308 KB Output is correct
63 Correct 442 ms 73436 KB Output is correct
64 Correct 478 ms 73128 KB Output is correct
65 Correct 8 ms 15636 KB Output is correct
66 Correct 11 ms 15848 KB Output is correct
67 Correct 257 ms 43228 KB Output is correct
68 Correct 340 ms 56224 KB Output is correct
69 Correct 472 ms 69624 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 17496 KB Output is correct
3 Correct 6 ms 15080 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 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Correct 7 ms 15196 KB Output is correct
9 Correct 193 ms 45236 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33316 KB Output is correct
12 Correct 23 ms 21972 KB Output is correct
13 Correct 31 ms 19400 KB Output is correct
14 Correct 7 ms 15196 KB Output is correct
15 Correct 7 ms 15312 KB Output is correct
16 Correct 183 ms 45444 KB Output is correct
17 Correct 464 ms 74304 KB Output is correct
18 Correct 450 ms 74516 KB Output is correct
19 Correct 500 ms 67284 KB Output is correct
20 Correct 512 ms 66052 KB Output is correct
21 Correct 478 ms 64472 KB Output is correct
22 Correct 7 ms 17500 KB Output is correct
23 Correct 73 ms 26060 KB Output is correct
24 Correct 26 ms 17112 KB Output is correct
25 Correct 92 ms 22380 KB Output is correct
26 Correct 164 ms 27024 KB Output is correct
27 Correct 270 ms 44052 KB Output is correct
28 Correct 321 ms 50676 KB Output is correct
29 Correct 402 ms 57248 KB Output is correct
30 Correct 482 ms 62948 KB Output is correct
31 Correct 531 ms 70432 KB Output is correct
32 Correct 507 ms 69660 KB Output is correct
33 Correct 424 ms 73336 KB Output is correct
34 Correct 9 ms 15684 KB Output is correct
35 Correct 12 ms 16092 KB Output is correct
36 Correct 221 ms 43044 KB Output is correct
37 Correct 344 ms 56256 KB Output is correct
38 Correct 499 ms 68512 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 17496 KB Output is correct
3 Correct 6 ms 15080 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 15196 KB Output is correct
7 Correct 6 ms 15196 KB Output is correct
8 Correct 7 ms 15196 KB Output is correct
9 Correct 193 ms 45236 KB Output is correct
10 Correct 17 ms 20448 KB Output is correct
11 Correct 69 ms 33316 KB Output is correct
12 Correct 23 ms 21972 KB Output is correct
13 Correct 31 ms 19400 KB Output is correct
14 Correct 7 ms 15196 KB Output is correct
15 Correct 7 ms 15312 KB Output is correct
16 Correct 183 ms 45444 KB Output is correct
17 Correct 8 ms 17496 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 8 ms 17500 KB Output is correct
20 Correct 10 ms 17636 KB Output is correct
21 Correct 6 ms 15196 KB Output is correct
22 Correct 8 ms 17500 KB Output is correct
23 Correct 465 ms 66460 KB Output is correct
24 Correct 9 ms 17752 KB Output is correct
25 Correct 9 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 157 ms 36868 KB Output is correct
29 Correct 250 ms 46996 KB Output is correct
30 Correct 350 ms 56660 KB Output is correct
31 Correct 465 ms 66420 KB Output is correct
32 Correct 7 ms 17496 KB Output is correct
33 Correct 8 ms 17500 KB Output is correct
34 Correct 8 ms 17500 KB Output is correct
35 Correct 7 ms 15196 KB Output is correct
36 Correct 7 ms 15196 KB Output is correct
37 Correct 8 ms 17500 KB Output is correct
38 Correct 8 ms 17500 KB Output is correct
39 Correct 8 ms 17652 KB Output is correct
40 Correct 7 ms 17496 KB Output is correct
41 Correct 6 ms 15192 KB Output is correct
42 Correct 7 ms 17652 KB Output is correct
43 Correct 8 ms 15448 KB Output is correct
44 Correct 8 ms 15556 KB Output is correct
45 Correct 201 ms 43260 KB Output is correct
46 Correct 355 ms 55292 KB Output is correct
47 Correct 296 ms 55288 KB Output is correct
48 Correct 8 ms 17500 KB Output is correct
49 Correct 7 ms 17500 KB Output is correct
50 Correct 7 ms 17496 KB Output is correct
51 Correct 7 ms 17500 KB Output is correct
52 Correct 9 ms 17500 KB Output is correct
53 Correct 7 ms 17456 KB Output is correct
54 Correct 7 ms 17500 KB Output is correct
55 Incorrect 399 ms 54668 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -