Submission #1064452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064452		beaconmc	Brought Down the Grading Server? (CEOI23_balance)	C++14	25 / 100	379 ms	42144 KiB

balance

#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;


map<ll,ll> sus;
map<ll,ll> sus2;
map<ll,ll> cnts;


set<vector<ll>> stuff[100005];

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,s,t;
	cin >> n >> s >> t;
	vector<vector<ll>> cores;
	vector<vector<ll>> orient(n);


	FOR(i,0,n){
		ll a,b;
		cin >> a >> b;

		cores.push_back({a,b});
		stuff[a].insert({b,i});
		stuff[b].insert({a,i});
		cnts[a]++;
		cnts[b]++;
	}

	ll cnt = 1;
	vector<ll> urg;
	FOR(i,1,n+1) if (stuff[i].size()==1) urg.push_back(i);


	while (cnt < n){
		if (stuff[cnt].size()==0) cnt++;
		ll cur = cnt;

		while (urg.size() && stuff[urg[urg.size()-1]].size() != 1) urg.pop_back();

		if (urg.size()){
			cur = urg[urg.size()-1];
			urg.pop_back();
		}
		ll pos = 0;
		if (sus[cur] == (cnts[cur]+1)/2){
			pos = 1;
		}

		while (1){
			if (stuff[cur].size()==0) break;

			vector<ll> node = (*stuff[cur].begin());
			if (pos==0){
				orient[node[1]] = {cur, node[0]};
				sus[cur]++;
				sus2[node[0]]++;
			}else{
				orient[node[1]] = {node[0], cur};
				sus[node[0]]++;
				sus2[cur]++;
			}


			stuff[cur].erase(node);
			stuff[node[0]].erase({cur, node[1]});

			if (stuff[cur].size() == 1) urg.push_back(cur);
			if (stuff[node[0]].size() == 1) urg.push_back(node[0]);

			cur = node[0];


			if (cur == cnt) break;
		}
	}

	for (auto&i : orient){
		cout << i[0] << " " << i[1] << "\n";
	}


	// cout << endl;

	// FOR(i,1,t+1){
	// 	cout << sus[i] << " " << sus2[i] << endl;
	// }






}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2-1: 15 / 15
• Subtask 2-2: 0 / 5
• Subtask 2-3: 0 / 5
• Subtask 3-1: 0 / 15
• Subtask 3-2: 0 / 5
• Subtask 3-3: 0 / 5
• Subtask 4-1: 0 / 20
• Subtask 4-2: 0 / 10
• Subtask 4-3: 0 / 10