oj.uz

Submission #791075

# Submission time Handle Problem Language Result Execution time Memory
791075 2023-07-23T11:44:48 Z doowey Parking (CEOI22_parking) C++17
28 / 100
 214 ms 55632 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;
const int M = (int)1e6 + 10;

set<int> empt;
int A[N][2];
bool vis[N][2];
vector<pii> pos[N];

struct elem{
	int idx;
	int up_pair;
	int cycle;
	
	bool operator< (const elem &ee) const {
		if(cycle == ee.cycle)
			return up_pair > ee.up_pair;
		else
			return cycle > ee.cycle;
	}
};


struct chain{
	vector<pii> C;
	int up_pair;
	bool cycle;
};

chain E[M];
int id;

vector<pii> trav;
int upper;

void dfs(int u, int v){
	vis[u][v]=true;
	trav.push_back(mp(u,v));
	if(A[u][(v^1)] != 0 && !vis[u][(v^1)]){
		dfs(u,(v^1));
		return;
	}
	for(auto x : pos[A[u][v]]){
		if(!vis[x.fi][x.se]){
			if((v & x.se) == 1) upper ++ ; // upper pair
			dfs(x.fi,x.se);
			return;
		}
	}	
}

vector<pii> oper;
priority_queue<elem> ee;

void solve_weak_chain(vector<pii> zz){
	if(zz.empty()) return;
	int l = 0;
	int r = (int)zz.size() - 1;
	while(l < r){
		if(zz[l].se == 0 && zz[l + 1].se == 1){
			oper.push_back(mp(zz[l + 1].fi, zz[l].fi)); // zz[l + 1].fi -> zz[l].fi
			l += 2 ;
		}
		else if(zz[r].se == 0 && zz[r - 1].se == 1){
			oper.push_back(mp(zz[r - 1].fi, zz[r].fi));
			r -= 2 ;
		}
		else{
			break;
		}
	}
	oper.push_back(mp(zz[l].fi, zz[r].fi));
	empt.insert(zz[l].fi);
}


int fin(){
	if(empt.empty()) {
		cout << "-1\n";
		exit(0);
		return -1;
	}
	int id = *empt.begin();
	empt.erase(empt.begin());
	return id;
}

void solve_chain(int id){
	vector<pii> pp;
	int chk;
	for(int i = 0 ; i < E[id].C.size(); i ++ ){
		if(i + 1 < E[id].C.size() && E[id].C[i].se == 1 && E[id].C[i + 1].se == 1){
			chk = fin();
			oper.push_back(mp(E[id].C[i].fi, chk));
			oper.push_back(mp(E[id].C[i + 1].fi, chk));
			solve_weak_chain(pp);
			pp.clear();
			i++;
			continue;
		}
		else{
			pp.push_back(E[id].C[i]);
		}
	}
	solve_weak_chain(pp);
}

void solve_cycle(int id){
	int j;
	int chk;
	vector<pii> tt;
	for(int i = 0 ; i < E[id].C.size(); i ++ ){
		j = (i + 1) % E[id].C.size();
		if(E[id].C[i].se == 1 && E[id].C[j].se == 1){
			chk = fin();
			oper.push_back(mp(E[id].C[i].fi, chk));
			oper.push_back(mp(E[id].C[j].fi, chk));
			for(int add = 1; add + 1 < E[id].C.size(); add ++ ){
				tt.push_back(E[id].C[(j + add) % E[id].C.size()]);
			}
			break;
		}
	}
	pii nw;
	if(tt.empty()){
		for(int i = 0 ; i < E[id].C.size(); i ++ ){
			j = (i + 1) % E[id].C.size();
			if(E[id].C[i].se == 1 && E[id].C[j].se == 0){
				chk = fin();
				oper.push_back(mp(E[id].C[j].fi, chk));
				nw = mp(chk, 0);
				tt.push_back(nw);
				for(int g = 0; g + 1 < E[id].C.size(); g ++ ){
					tt.push_back(E[id].C[(j + g) % E[id].C.size()]);
				}
				break;
			}
		}
	}
	int tp = 0;
	for(int i = 0 ; i + 1 < tt.size(); i ++ ){
		if((tt[i].se & tt[i + 1].se) == 1){
			tp ++ ;
		}
	}
	E[id] = {tt, tp, false};
	ee.push({id, tp, false});
	id ++ ;
}

void solve(int id){
	if(E[id].cycle) solve_cycle(id);
	else solve_chain(id);
}

int main(){
	fastIO;
	int n, m;
	cin >> n >> m;
	int x, y;
	for(int i = 1; i <= m; i ++ ){
		cin >> x >> y;
		if(x == 0 && y == 0) empt.insert(i);
		else{
			if(x==y) continue; // we dont look at et
			A[i][0] = x;
			A[i][1] = y;
			for(int j = 0 ; j < 2; j ++ ){
				if(A[i][j] != 0)pos[A[i][j]].push_back(mp(i,j));
			}
		}
	}
	
	for(int i = 1; i <= m; i ++ ){
		if(A[i][0] != 0 && A[i][1] == 0 && !vis[i][0]){
			// NO cycle
			trav.clear();
			upper = 0;
			
			dfs(i,0);
			
			E[id] = {trav, upper, false};
			ee.push({id, upper, false});
			id ++ ;
		}
	}
	for(int i = 1; i <= m; i ++ ){
		if(A[i][0] != 0 && !vis[i][0]){
			// cycle?
			trav.clear();
			upper = 0;
			
			dfs(i,0);
			
			E[id] = {trav, upper, true};
			ee.push({id, upper, true});
			id ++ ;
		}
	}
	elem U;
	while(!ee.empty()){
		U = ee.top();
		ee.pop();
		solve(U.idx);
	}
	cout << oper.size() << "\n";
	for(auto xx : oper){
		cout << xx.fi << " " << xx.se << "\n";
	}
	return 0;
}

Compilation message

Main.cpp: In function 'void solve_chain(int)':
Main.cpp:102:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0 ; i < E[id].C.size(); i ++ ){
      |                  ~~^~~~~~~~~~~~~~~~
Main.cpp:103:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   if(i + 1 < E[id].C.size() && E[id].C[i].se == 1 && E[id].C[i + 1].se == 1){
      |      ~~~~~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'void solve_cycle(int)':
Main.cpp:123:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i = 0 ; i < E[id].C.size(); i ++ ){
      |                  ~~^~~~~~~~~~~~~~~~
Main.cpp:129:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |    for(int add = 1; add + 1 < E[id].C.size(); add ++ ){
      |                     ~~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:137:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |   for(int i = 0 ; i < E[id].C.size(); i ++ ){
      |                   ~~^~~~~~~~~~~~~~~~
Main.cpp:144:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for(int g = 0; g + 1 < E[id].C.size(); g ++ ){
      |                    ~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:152:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |  for(int i = 0 ; i + 1 < tt.size(); i ++ ){
      |                  ~~~~~~^~~~~~~~~~~

Subtask #1
2.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36284 KB Output is correct
2 Correct 17 ms 36356 KB Output is correct
3 Correct 17 ms 36336 KB Output is correct
4 Partially correct 15 ms 36308 KB Output is partially correct
5 Correct 16 ms 36308 KB Output is correct
6 Correct 16 ms 36236 KB Output is correct
7 Correct 16 ms 36344 KB Output is correct
8 Correct 22 ms 36320 KB Output is correct
9 Correct 18 ms 36252 KB Output is correct
10 Correct 18 ms 36336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 51656 KB Output is correct
2 Correct 122 ms 52228 KB Output is correct
3 Correct 101 ms 50872 KB Output is correct
4 Correct 94 ms 50748 KB Output is correct
5 Correct 110 ms 52480 KB Output is correct

Subtask #3
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 36308 KB Output is partially correct
2 Correct 17 ms 36336 KB Output is correct
3 Correct 18 ms 36340 KB Output is correct
4 Partially correct 18 ms 36436 KB Output is partially correct
5 Correct 22 ms 36300 KB Output is correct
6 Correct 22 ms 36340 KB Output is correct
7 Partially correct 20 ms 36436 KB Output is partially correct
8 Correct 17 ms 36308 KB Output is correct
9 Partially correct 19 ms 36440 KB Output is partially correct

Subtask #4
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 36308 KB Output is partially correct
2 Correct 17 ms 36336 KB Output is correct
3 Correct 18 ms 36340 KB Output is correct
4 Partially correct 18 ms 36436 KB Output is partially correct
5 Correct 22 ms 36300 KB Output is correct
6 Correct 22 ms 36340 KB Output is correct
7 Partially correct 20 ms 36436 KB Output is partially correct
8 Correct 17 ms 36308 KB Output is correct
9 Partially correct 19 ms 36440 KB Output is partially correct
10 Partially correct 214 ms 55632 KB Output is partially correct
11 Correct 42 ms 38648 KB Output is correct
12 Correct 153 ms 49776 KB Output is correct
13 Partially correct 153 ms 54124 KB Output is partially correct
14 Correct 122 ms 50204 KB Output is correct
15 Correct 141 ms 49716 KB Output is correct
16 Partially correct 191 ms 55516 KB Output is partially correct
17 Correct 107 ms 50788 KB Output is correct
18 Partially correct 203 ms 55076 KB Output is partially correct

Subtask #5
5.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 36436 KB Output is correct
2 Correct 18 ms 36328 KB Output is correct
3 Correct 22 ms 36368 KB Output is correct
4 Partially correct 20 ms 36308 KB Output is partially correct
5 Correct 19 ms 36340 KB Output is correct
6 Correct 19 ms 36432 KB Output is correct
7 Correct 21 ms 36348 KB Output is correct
8 Correct 24 ms 36340 KB Output is correct
9 Correct 23 ms 36332 KB Output is correct
10 Correct 19 ms 36308 KB Output is correct
11 Partially correct 19 ms 36320 KB Output is partially correct
12 Partially correct 19 ms 36436 KB Output is partially correct
13 Correct 18 ms 36328 KB Output is correct
14 Correct 22 ms 36336 KB Output is correct
15 Correct 18 ms 36320 KB Output is correct
16 Partially correct 21 ms 36436 KB Output is partially correct
17 Correct 19 ms 36308 KB Output is correct
18 Partially correct 18 ms 36344 KB Output is partially correct
19 Partially correct 18 ms 36336 KB Output is partially correct
20 Partially correct 21 ms 36344 KB Output is partially correct
21 Correct 18 ms 36324 KB Output is correct
22 Partially correct 19 ms 36428 KB Output is partially correct
23 Correct 22 ms 36332 KB Output is correct
24 Partially correct 19 ms 36340 KB Output is partially correct

Subtask #6
3.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 36284 KB Output is correct
2 Correct 17 ms 36356 KB Output is correct
3 Correct 17 ms 36336 KB Output is correct
4 Partially correct 15 ms 36308 KB Output is partially correct
5 Correct 16 ms 36308 KB Output is correct
6 Correct 16 ms 36236 KB Output is correct
7 Correct 16 ms 36344 KB Output is correct
8 Correct 22 ms 36320 KB Output is correct
9 Correct 18 ms 36252 KB Output is correct
10 Correct 18 ms 36336 KB Output is correct
11 Correct 111 ms 51656 KB Output is correct
12 Correct 122 ms 52228 KB Output is correct
13 Correct 101 ms 50872 KB Output is correct
14 Correct 94 ms 50748 KB Output is correct
15 Correct 110 ms 52480 KB Output is correct
16 Partially correct 16 ms 36308 KB Output is partially correct
17 Correct 17 ms 36336 KB Output is correct
18 Correct 18 ms 36340 KB Output is correct
19 Partially correct 18 ms 36436 KB Output is partially correct
20 Correct 22 ms 36300 KB Output is correct
21 Correct 22 ms 36340 KB Output is correct
22 Partially correct 20 ms 36436 KB Output is partially correct
23 Correct 17 ms 36308 KB Output is correct
24 Partially correct 19 ms 36440 KB Output is partially correct
25 Partially correct 214 ms 55632 KB Output is partially correct
26 Correct 42 ms 38648 KB Output is correct
27 Correct 153 ms 49776 KB Output is correct
28 Partially correct 153 ms 54124 KB Output is partially correct
29 Correct 122 ms 50204 KB Output is correct
30 Correct 141 ms 49716 KB Output is correct
31 Partially correct 191 ms 55516 KB Output is partially correct
32 Correct 107 ms 50788 KB Output is correct
33 Partially correct 203 ms 55076 KB Output is partially correct
34 Correct 18 ms 36436 KB Output is correct
35 Correct 18 ms 36328 KB Output is correct
36 Correct 22 ms 36368 KB Output is correct
37 Partially correct 20 ms 36308 KB Output is partially correct
38 Correct 19 ms 36340 KB Output is correct
39 Correct 19 ms 36432 KB Output is correct
40 Correct 21 ms 36348 KB Output is correct
41 Correct 24 ms 36340 KB Output is correct
42 Correct 23 ms 36332 KB Output is correct
43 Correct 19 ms 36308 KB Output is correct
44 Partially correct 19 ms 36320 KB Output is partially correct
45 Partially correct 19 ms 36436 KB Output is partially correct
46 Correct 18 ms 36328 KB Output is correct
47 Correct 22 ms 36336 KB Output is correct
48 Correct 18 ms 36320 KB Output is correct
49 Partially correct 21 ms 36436 KB Output is partially correct
50 Correct 19 ms 36308 KB Output is correct
51 Partially correct 18 ms 36344 KB Output is partially correct
52 Partially correct 18 ms 36336 KB Output is partially correct
53 Partially correct 21 ms 36344 KB Output is partially correct
54 Correct 18 ms 36324 KB Output is correct
55 Partially correct 19 ms 36428 KB Output is partially correct
56 Correct 22 ms 36332 KB Output is correct
57 Partially correct 19 ms 36340 KB Output is partially correct
58 Partially correct 135 ms 54524 KB Output is partially correct
59 Correct 157 ms 54976 KB Output is correct
60 Correct 141 ms 53876 KB Output is correct
61 Partially correct 163 ms 54316 KB Output is partially correct
62 Correct 44 ms 38740 KB Output is correct
63 Correct 153 ms 53652 KB Output is correct
64 Correct 114 ms 49988 KB Output is correct
65 Correct 130 ms 54576 KB Output is correct
66 Correct 140 ms 55340 KB Output is correct
67 Correct 145 ms 49436 KB Output is correct
68 Partially correct 161 ms 54328 KB Output is partially correct
69 Partially correct 141 ms 53868 KB Output is partially correct
70 Correct 94 ms 49496 KB Output is correct
71 Correct 102 ms 50000 KB Output is correct
72 Correct 111 ms 49760 KB Output is correct
73 Partially correct 151 ms 55512 KB Output is partially correct
74 Correct 139 ms 49668 KB Output is correct
75 Partially correct 169 ms 55016 KB Output is partially correct
76 Partially correct 160 ms 55344 KB Output is partially correct
77 Partially correct 178 ms 54820 KB Output is partially correct
78 Correct 100 ms 49900 KB Output is correct
79 Partially correct 134 ms 54632 KB Output is partially correct
80 Correct 99 ms 50788 KB Output is correct
81 Partially correct 138 ms 54764 KB Output is partially correct