Submission #791078

#	Time	Username	Problem	Language	Result	Execution time	Memory
791078		doowey	Parking (CEOI22_parking)	C++17	100 / 100	219 ms	53080 KiB

Main

#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[i].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 (stderr)

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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15