oj.uz

Submission #233546

# Submission time Handle Problem Language Result Execution time Memory
233546 2020-05-20T21:09:41 Z alishahali1382 Teoretičar (COCI18_teoreticar) C++14
130 / 130
 4554 ms 32108 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 8 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 7 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 5376 KB Output is correct
2 Correct 11 ms 5248 KB Output is correct
3 Correct 11 ms 5376 KB Output is correct
4 Correct 9 ms 5248 KB Output is correct
5 Correct 9 ms 5248 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 5248 KB Output is correct
2 Correct 11 ms 5248 KB Output is correct
3 Correct 12 ms 5376 KB Output is correct
4 Correct 11 ms 5248 KB Output is correct
5 Correct 9 ms 5248 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 18652 KB Output is correct
2 Correct 3501 ms 32108 KB Output is correct
3 Correct 1205 ms 30384 KB Output is correct
4 Correct 586 ms 24184 KB Output is correct
5 Correct 458 ms 18552 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 607 ms 18564 KB Output is correct
2 Correct 1203 ms 30328 KB Output is correct
3 Correct 1860 ms 30584 KB Output is correct
4 Correct 597 ms 24312 KB Output is correct
5 Correct 121 ms 9208 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1577 ms 23504 KB Output is correct
2 Correct 2335 ms 31424 KB Output is correct
3 Correct 92 ms 9080 KB Output is correct
4 Correct 814 ms 22264 KB Output is correct
5 Correct 159 ms 17784 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1112 ms 21068 KB Output is correct
2 Correct 3847 ms 26288 KB Output is correct
3 Correct 2296 ms 30328 KB Output is correct
4 Correct 814 ms 25336 KB Output is correct
5 Correct 568 ms 24184 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 17528 KB Output is correct
2 Correct 4554 ms 26872 KB Output is correct
3 Correct 2912 ms 31608 KB Output is correct
4 Correct 871 ms 25336 KB Output is correct
5 Correct 829 ms 21972 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 912 ms 17652 KB Output is correct
2 Correct 4333 ms 26872 KB Output is correct
3 Correct 1989 ms 31156 KB Output is correct
4 Correct 171 ms 9464 KB Output is correct
5 Correct 808 ms 21752 KB Output is correct