제출 #233546

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
233546		alishahali1382	Teoretičar (COCI18_teoreticar)	C++14	130 / 130	4554 ms	32108 KiB

teoreticar

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int MAXN=100010, LOG=20;

int n, nn, m, k, u, v, x, y, t, a, b;
int A[MAXN*2], deg[MAXN*2];
int E[MAXN*5][2];
int P[MAXN*5], color[MAXN*5], pw;
bool mark[MAXN*5];
vector<int> G[MAXN*2];

void tour(int node){
	while (G[node].size()){
		int id=G[node].back();
		G[node].pop_back();
		if (mark[id]) continue ;
		mark[id]=1;
		int v=(node^E[id][0]^E[id][1]);
		deg[node]--;
		deg[v]--;
		if (node<n) color[id]|=(1<<pw);
		//debug(id)
		// add edge
		tour(v);
		return ;
	}
}

void Solve(int tl, int tr){
	//memset(deg, 0, sizeof(deg));
	bool good=1;
	for (int i=tl; i<tr; i++){
		mark[P[i]]=0;
		deg[E[P[i]][0]]=0;
		deg[E[P[i]][1]]=0;
		G[E[P[i]][0]].clear();
		G[E[P[i]][1]].clear();
	}
	for (int i=tl; i<tr; i++)for (int t:{0, 1}){
		G[E[P[i]][t]].pb(P[i]);
		if (deg[E[P[i]][t]]++) good=0;
	}
	
	if (good) return ;
	/*
	debug2(tl, tr)
	for (int i=tl; i<tr; i++) debug2(P[i], color[P[i]])
	debug(pw)
	cerr<<'\n';
	*/
	for (int i=tl; i<tr; i++) for (int t:{0, 1}){
		if (deg[E[P[i]][t]]&1) tour(E[P[i]][t]);
	}
	for (int i=tl; i<tr; i++) for (int t:{0, 1}){
		tour(E[P[i]][t]);
	}
	for (int i=tl; i<tr; i++) mark[P[i]]=1;
	sort(P+tl, P+tr, [](int i, int j){
		return color[i]<color[j];
	});
	
	for (int i=tl+1; i<tr; i++) if (color[P[i]]!=color[P[i-1]]){
		pw++;
		Solve(tl, i);
		Solve(i, tr);
		pw--;
		return ;
	}
	
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>nn>>m;
	for (int i=1; i<=m; i++){
		cin>>E[i][0]>>E[i][1];
		E[i][0]--;
		E[i][1]--;
		E[i][1]+=n;
		P[i]=i;
		//debug2(E[i][0], E[i][1])
	}
	Solve(1, m+1);
	cout<<(*max_element(color+1, color+m+1))+1<<'\n';
	for (int i=1; i<=m; i++) cout<<color[i]+1<<'\n';
	
	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 13 / 13
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13
• Subtask 9: 13 / 13
• Subtask 10: 13 / 13