oj.uz

답안 #1059662

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1059662 2024-08-15T06:52:04 Z pcc 분수 공원 (IOI21_parks) C++17
55 / 100
 552 ms 74380 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){
	for(auto nxt:lef[now]){
		if(my[nxt] == -1){
			my[nxt] = now;
			mx[now] = nxt;
			break;
		}
	}
	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<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:89: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]
   89 |  if(edges.size() != N-1)return 0;
      |     ~~~~~~~~~~~~~^~~~~~
parks.cpp:90: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]
   90 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:105: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]
  105 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:130: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]
  130 |  for(int i = 0;i<all.size();i++){
      |                ~^~~~~~~~~~~
parks.cpp:153: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]
  153 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~
parks.cpp:158: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]
  158 |  for(int i = 0;i<edges.size();i++){
      |                ~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15316 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 17656 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15092 KB Output is correct
7 Correct 6 ms 15136 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 187 ms 45344 KB Output is correct
10 Correct 20 ms 20448 KB Output is correct
11 Correct 71 ms 33348 KB Output is correct
12 Correct 22 ms 21980 KB Output is correct
13 Correct 31 ms 19416 KB Output is correct
14 Correct 7 ms 15192 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 180 ms 45360 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15316 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 17656 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15092 KB Output is correct
7 Correct 6 ms 15136 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 187 ms 45344 KB Output is correct
10 Correct 20 ms 20448 KB Output is correct
11 Correct 71 ms 33348 KB Output is correct
12 Correct 22 ms 21980 KB Output is correct
13 Correct 31 ms 19416 KB Output is correct
14 Correct 7 ms 15192 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 180 ms 45360 KB Output is correct
17 Correct 7 ms 17500 KB Output is correct
18 Correct 7 ms 17556 KB Output is correct
19 Correct 7 ms 17500 KB Output is correct
20 Correct 7 ms 17500 KB Output is correct
21 Correct 7 ms 15208 KB Output is correct
22 Correct 7 ms 17500 KB Output is correct
23 Correct 452 ms 66460 KB Output is correct
24 Correct 7 ms 17496 KB Output is correct
25 Correct 8 ms 17756 KB Output is correct
26 Correct 8 ms 15448 KB Output is correct
27 Correct 8 ms 15452 KB Output is correct
28 Correct 155 ms 36964 KB Output is correct
29 Correct 245 ms 46996 KB Output is correct
30 Correct 391 ms 56720 KB Output is correct
31 Correct 499 ms 66532 KB Output is correct
32 Correct 7 ms 17624 KB Output is correct
33 Correct 9 ms 17756 KB Output is correct
34 Correct 7 ms 17500 KB Output is correct
35 Correct 8 ms 15196 KB Output is correct
36 Correct 6 ms 15244 KB Output is correct
37 Correct 7 ms 17496 KB Output is correct
38 Correct 7 ms 17572 KB Output is correct
39 Correct 7 ms 17500 KB Output is correct
40 Correct 7 ms 17500 KB Output is correct
41 Correct 6 ms 15184 KB Output is correct
42 Correct 7 ms 17500 KB Output is correct
43 Correct 7 ms 15324 KB Output is correct
44 Correct 8 ms 15452 KB Output is correct
45 Correct 203 ms 43248 KB Output is correct
46 Correct 310 ms 55068 KB Output is correct
47 Correct 303 ms 55148 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15316 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 17656 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15092 KB Output is correct
7 Correct 6 ms 15136 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 187 ms 45344 KB Output is correct
10 Correct 20 ms 20448 KB Output is correct
11 Correct 71 ms 33348 KB Output is correct
12 Correct 22 ms 21980 KB Output is correct
13 Correct 31 ms 19416 KB Output is correct
14 Correct 7 ms 15192 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 180 ms 45360 KB Output is correct
17 Correct 7 ms 17500 KB Output is correct
18 Correct 7 ms 17556 KB Output is correct
19 Correct 7 ms 17500 KB Output is correct
20 Correct 7 ms 17500 KB Output is correct
21 Correct 7 ms 15208 KB Output is correct
22 Correct 7 ms 17500 KB Output is correct
23 Correct 452 ms 66460 KB Output is correct
24 Correct 7 ms 17496 KB Output is correct
25 Correct 8 ms 17756 KB Output is correct
26 Correct 8 ms 15448 KB Output is correct
27 Correct 8 ms 15452 KB Output is correct
28 Correct 155 ms 36964 KB Output is correct
29 Correct 245 ms 46996 KB Output is correct
30 Correct 391 ms 56720 KB Output is correct
31 Correct 499 ms 66532 KB Output is correct
32 Correct 7 ms 17624 KB Output is correct
33 Correct 9 ms 17756 KB Output is correct
34 Correct 7 ms 17500 KB Output is correct
35 Correct 8 ms 15196 KB Output is correct
36 Correct 6 ms 15244 KB Output is correct
37 Correct 7 ms 17496 KB Output is correct
38 Correct 7 ms 17572 KB Output is correct
39 Correct 7 ms 17500 KB Output is correct
40 Correct 7 ms 17500 KB Output is correct
41 Correct 6 ms 15184 KB Output is correct
42 Correct 7 ms 17500 KB Output is correct
43 Correct 7 ms 15324 KB Output is correct
44 Correct 8 ms 15452 KB Output is correct
45 Correct 203 ms 43248 KB Output is correct
46 Correct 310 ms 55068 KB Output is correct
47 Correct 303 ms 55148 KB Output is correct
48 Correct 7 ms 17500 KB Output is correct
49 Correct 7 ms 17448 KB Output is correct
50 Correct 9 ms 17500 KB Output is correct
51 Correct 7 ms 17496 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 Incorrect 427 ms 53768 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15316 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 17656 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15092 KB Output is correct
7 Correct 6 ms 15136 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 187 ms 45344 KB Output is correct
10 Correct 20 ms 20448 KB Output is correct
11 Correct 71 ms 33348 KB Output is correct
12 Correct 22 ms 21980 KB Output is correct
13 Correct 31 ms 19416 KB Output is correct
14 Correct 7 ms 15192 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 180 ms 45360 KB Output is correct
17 Correct 8 ms 17496 KB Output is correct
18 Correct 7 ms 17500 KB Output is correct
19 Correct 6 ms 15116 KB Output is correct
20 Correct 436 ms 67428 KB Output is correct
21 Correct 419 ms 67172 KB Output is correct
22 Correct 427 ms 67100 KB Output is correct
23 Correct 344 ms 65756 KB Output is correct
24 Correct 190 ms 32504 KB Output is correct
25 Correct 260 ms 34036 KB Output is correct
26 Correct 228 ms 33988 KB Output is correct
27 Correct 450 ms 73376 KB Output is correct
28 Correct 447 ms 73248 KB Output is correct
29 Correct 507 ms 73004 KB Output is correct
30 Correct 513 ms 73100 KB Output is correct
31 Correct 7 ms 17496 KB Output is correct
32 Correct 31 ms 21204 KB Output is correct
33 Correct 79 ms 24192 KB Output is correct
34 Correct 420 ms 67572 KB Output is correct
35 Correct 14 ms 16216 KB Output is correct
36 Correct 57 ms 20172 KB Output is correct
37 Correct 121 ms 25032 KB Output is correct
38 Correct 168 ms 38352 KB Output is correct
39 Correct 242 ms 45540 KB Output is correct
40 Correct 335 ms 54432 KB Output is correct
41 Correct 431 ms 61748 KB Output is correct
42 Correct 492 ms 68912 KB Output is correct
43 Correct 7 ms 17500 KB Output is correct
44 Correct 7 ms 17452 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 7 ms 17620 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 17564 KB Output is correct
52 Correct 6 ms 15072 KB Output is correct
53 Correct 7 ms 17500 KB Output is correct
54 Correct 7 ms 15452 KB Output is correct
55 Correct 8 ms 15584 KB Output is correct
56 Correct 205 ms 43216 KB Output is correct
57 Correct 301 ms 55244 KB Output is correct
58 Correct 304 ms 55180 KB Output is correct
59 Correct 6 ms 15192 KB Output is correct
60 Correct 7 ms 17500 KB Output is correct
61 Correct 6 ms 15316 KB Output is correct
62 Correct 413 ms 73500 KB Output is correct
63 Correct 411 ms 73368 KB Output is correct
64 Correct 415 ms 73008 KB Output is correct
65 Correct 8 ms 15448 KB Output is correct
66 Correct 11 ms 15964 KB Output is correct
67 Correct 202 ms 43452 KB Output is correct
68 Correct 331 ms 56116 KB Output is correct
69 Correct 473 ms 69660 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15316 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 17656 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15092 KB Output is correct
7 Correct 6 ms 15136 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 187 ms 45344 KB Output is correct
10 Correct 20 ms 20448 KB Output is correct
11 Correct 71 ms 33348 KB Output is correct
12 Correct 22 ms 21980 KB Output is correct
13 Correct 31 ms 19416 KB Output is correct
14 Correct 7 ms 15192 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 180 ms 45360 KB Output is correct
17 Correct 431 ms 74268 KB Output is correct
18 Correct 420 ms 74380 KB Output is correct
19 Correct 454 ms 66840 KB Output is correct
20 Correct 530 ms 66108 KB Output is correct
21 Correct 496 ms 64332 KB Output is correct
22 Correct 7 ms 17500 KB Output is correct
23 Correct 71 ms 25928 KB Output is correct
24 Correct 25 ms 17108 KB Output is correct
25 Correct 87 ms 22240 KB Output is correct
26 Correct 151 ms 27112 KB Output is correct
27 Correct 260 ms 43920 KB Output is correct
28 Correct 322 ms 50632 KB Output is correct
29 Correct 399 ms 57228 KB Output is correct
30 Correct 477 ms 62752 KB Output is correct
31 Correct 552 ms 70564 KB Output is correct
32 Correct 468 ms 69660 KB Output is correct
33 Correct 425 ms 73424 KB Output is correct
34 Correct 9 ms 15708 KB Output is correct
35 Correct 12 ms 15964 KB Output is correct
36 Correct 208 ms 43052 KB Output is correct
37 Correct 322 ms 56220 KB Output is correct
38 Correct 482 ms 68636 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 15316 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 17656 KB Output is correct
5 Correct 7 ms 17500 KB Output is correct
6 Correct 6 ms 15092 KB Output is correct
7 Correct 6 ms 15136 KB Output is correct
8 Correct 6 ms 15196 KB Output is correct
9 Correct 187 ms 45344 KB Output is correct
10 Correct 20 ms 20448 KB Output is correct
11 Correct 71 ms 33348 KB Output is correct
12 Correct 22 ms 21980 KB Output is correct
13 Correct 31 ms 19416 KB Output is correct
14 Correct 7 ms 15192 KB Output is correct
15 Correct 7 ms 15452 KB Output is correct
16 Correct 180 ms 45360 KB Output is correct
17 Correct 7 ms 17500 KB Output is correct
18 Correct 7 ms 17556 KB Output is correct
19 Correct 7 ms 17500 KB Output is correct
20 Correct 7 ms 17500 KB Output is correct
21 Correct 7 ms 15208 KB Output is correct
22 Correct 7 ms 17500 KB Output is correct
23 Correct 452 ms 66460 KB Output is correct
24 Correct 7 ms 17496 KB Output is correct
25 Correct 8 ms 17756 KB Output is correct
26 Correct 8 ms 15448 KB Output is correct
27 Correct 8 ms 15452 KB Output is correct
28 Correct 155 ms 36964 KB Output is correct
29 Correct 245 ms 46996 KB Output is correct
30 Correct 391 ms 56720 KB Output is correct
31 Correct 499 ms 66532 KB Output is correct
32 Correct 7 ms 17624 KB Output is correct
33 Correct 9 ms 17756 KB Output is correct
34 Correct 7 ms 17500 KB Output is correct
35 Correct 8 ms 15196 KB Output is correct
36 Correct 6 ms 15244 KB Output is correct
37 Correct 7 ms 17496 KB Output is correct
38 Correct 7 ms 17572 KB Output is correct
39 Correct 7 ms 17500 KB Output is correct
40 Correct 7 ms 17500 KB Output is correct
41 Correct 6 ms 15184 KB Output is correct
42 Correct 7 ms 17500 KB Output is correct
43 Correct 7 ms 15324 KB Output is correct
44 Correct 8 ms 15452 KB Output is correct
45 Correct 203 ms 43248 KB Output is correct
46 Correct 310 ms 55068 KB Output is correct
47 Correct 303 ms 55148 KB Output is correct
48 Correct 7 ms 17500 KB Output is correct
49 Correct 7 ms 17448 KB Output is correct
50 Correct 9 ms 17500 KB Output is correct
51 Correct 7 ms 17496 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 Incorrect 427 ms 53768 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -