oj.uz

Submission #82900

# Submission time Handle Problem Language Result Execution time Memory
82900 2018-11-02T18:25:14 Z georgerapeanu Teoretičar (COCI18_teoreticar) C++11
0 / 130
 4266 ms 63120 KB 
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int NMAX = 2e5;
const int MMAX = 5e5;
 
 
vector< pair<int,int> > graph[NMAX + 5];
int gr[NMAX + 5];
 
int ans[MMAX + 5];
 
vector<pair<pair<int,int>,int> > euler;
bool used[MMAX + 5];
 
void get_euler(int node,bool dump){
	if(dump){
		euler.clear();
	}
	
	vector<pair<int,pair<pair<int,int>,int> > > st;
	
	st.push_back({node,{{0,0},0}});
	
	while(!st.empty()){
		node = st.back().first;
		pair<pair<int,int>,int> edge = st.back().second;
		
		while(!graph[node].empty() && used[graph[node].back().second]){
			graph[node].pop_back();
		}
		
		if(graph[node].empty()){
			euler.push_back(edge);
			st.pop_back();
		}
		else{
			int it = graph[node].back().first;
			int id = graph[node].back().second;
			graph[node].pop_back();
			used[id] = true;
			st.push_back(make_pair(it,make_pair(make_pair(node,it),id)));
		}
	}
}
 
void solve(vector< pair<pair<int,int>,int> > &edges,int &last_cul){
	random_shuffle(edges.begin(),edges.end());
	int ma = 0;
	for(auto it:edges){
		gr[it.first.first]++;
		gr[it.first.second]++;
		
		graph[it.first.first].push_back({it.first.second,it.second});
		graph[it.first.second].push_back({it.first.first,it.second});
		
		ma = max(ma,gr[it.first.first]);
		ma = max(ma,gr[it.first.second]);
	}
	
	if(ma <= 1){
		last_cul++;
		for(auto it:edges){
			ans[it.second] = last_cul;
			gr[it.first.first] = 0;
			gr[it.first.second] = 0;
			graph[it.first.first].clear();
			graph[it.first.second].clear();
		}
		return ;
	}
	
	int fst_virtual = NMAX + 1;
	int snd_virtual = NMAX + 2;
	
	for(auto it:edges){
		if(gr[it.first.first] % 2 == 1){
			gr[it.first.first]++;
			gr[snd_virtual]++;
			
			graph[it.first.first].push_back({snd_virtual,0});
			graph[snd_virtual].push_back({it.first.first,0});
		}
		
		if(gr[it.first.second] % 2 == 1){
			gr[it.first.second]++;
			gr[fst_virtual]++;
			
			graph[it.first.second].push_back({fst_virtual,0});
			graph[fst_virtual].push_back({it.first.second,0});
		}
	}
	
	used[0] = false;
	
	for(auto it:edges){
		used[it.second] = false;
	}
	
	get_euler(fst_virtual,1);
	get_euler(snd_virtual,0);
	
	for(auto it:edges){
		get_euler(it.first.first,0);
		get_euler(it.first.second,0);
	}
	
	vector<pair<pair<int,int>,int> > x[2];
	
	for(int i = 0;i < (int)euler.size();i++){
		if(!euler[i].second){
			continue;
		}	
		x[i & 1].push_back(euler[i]);
	}
	
	for(auto it:edges){
		gr[it.first.first] = 0;
		gr[it.first.second] = 0;
		graph[it.first.second].clear();
		graph[it.first.first].clear();
	}
	
	graph[fst_virtual].clear();gr[fst_virtual] = 0;
	graph[snd_virtual].clear();gr[snd_virtual] = 0;
	
	solve(x[0],last_cul);
	solve(x[1],last_cul);
}
 
int main(){
	
	srand(time(NULL));
	
	int l,r,m;
	
	scanf("%d %d %d",&l,&r,&m);
	
	vector<pair<pair<int,int>,int> > edges;
	
	for(int i = 1;i <= m;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		y += l;
		edges.push_back({{x,y},i});
	}
	
	int last_cul = 0;
	
	solve(edges,last_cul);
	
	printf("%d\n",last_cul);
	
	for(int i = 1;i <= m;i++){
		printf("%d\n",ans[i]);
	}
	
	return 0;
}

Compilation message

teoreticar.cpp: In function 'int main()':
teoreticar.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&l,&r,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:148:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 4984 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5116 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 5844 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 5844 KB Output is correct
2 Incorrect 15 ms 6004 KB too many colors
3 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1584 ms 51880 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1749 ms 51880 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3547 ms 63120 KB Output is correct
2 Incorrect 4266 ms 63120 KB too many colors
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2041 ms 63120 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1743 ms 63120 KB too many colors
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1702 ms 63120 KB too many colors
2 Halted 0 ms 0 KB -