oj.uz

Submission #82906

# Submission time Handle Problem Language Result Execution time Memory
82906 2018-11-02T18:54:21 Z georgerapeanu Teoretičar (COCI18_teoreticar) C++11
130 / 130
 6214 ms 166856 KB 
#include <cstdio>
#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[2 * 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},MMAX + 1}});
	
	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){
	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;
	
	vector<int> papers_pls;
	int last_id = MMAX + 2;
	
	for(auto it:edges){
		if(gr[it.first.first] % 2 == 1){
			gr[it.first.first]++;
			gr[snd_virtual]++;
			
			last_id++;
			papers_pls.push_back(last_id);
			graph[it.first.first].push_back({snd_virtual,last_id});
			graph[snd_virtual].push_back({it.first.first,last_id});
		}
		
		if(gr[it.first.second] % 2 == 1){
			gr[it.first.second]++;
			gr[fst_virtual]++;
			
			last_id++;
			papers_pls.push_back(last_id);
			
			graph[it.first.second].push_back({fst_virtual,last_id});
			graph[fst_virtual].push_back({it.first.second,last_id});
		}
	}
	
	for(auto it:papers_pls){
		used[it] = false;
	}
	
	used[MMAX + 1] = false;
	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 > MMAX){
			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(){
	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:149: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:155: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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4984 KB Output is correct
2 Correct 6 ms 5112 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 6 ms 5324 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5324 KB Output is correct
2 Correct 6 ms 5324 KB Output is correct
3 Correct 6 ms 5324 KB Output is correct
4 Correct 6 ms 5324 KB Output is correct
5 Correct 6 ms 5324 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6184 KB Output is correct
2 Correct 15 ms 6184 KB Output is correct
3 Correct 17 ms 6336 KB Output is correct
4 Correct 9 ms 6336 KB Output is correct
5 Correct 18 ms 6336 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 6336 KB Output is correct
2 Correct 15 ms 6336 KB Output is correct
3 Correct 18 ms 6512 KB Output is correct
4 Correct 12 ms 6512 KB Output is correct
5 Correct 9 ms 6512 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 896 ms 52360 KB Output is correct
2 Correct 5774 ms 80404 KB Output is correct
3 Correct 1837 ms 83700 KB Output is correct
4 Correct 898 ms 83700 KB Output is correct
5 Correct 785 ms 83700 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 83700 KB Output is correct
2 Correct 1915 ms 97908 KB Output is correct
3 Correct 3193 ms 102348 KB Output is correct
4 Correct 946 ms 102348 KB Output is correct
5 Correct 208 ms 102348 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4054 ms 106792 KB Output is correct
2 Correct 4009 ms 110336 KB Output is correct
3 Correct 174 ms 110336 KB Output is correct
4 Correct 1250 ms 110336 KB Output is correct
5 Correct 267 ms 110336 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1680 ms 110336 KB Output is correct
2 Correct 5861 ms 123964 KB Output is correct
3 Correct 3663 ms 127736 KB Output is correct
4 Correct 1180 ms 127736 KB Output is correct
5 Correct 882 ms 127736 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1579 ms 127736 KB Output is correct
2 Correct 6214 ms 143816 KB Output is correct
3 Correct 5250 ms 149160 KB Output is correct
4 Correct 1228 ms 149160 KB Output is correct
5 Correct 1206 ms 149160 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1581 ms 149160 KB Output is correct
2 Correct 6071 ms 161436 KB Output is correct
3 Correct 3449 ms 166856 KB Output is correct
4 Correct 257 ms 166856 KB Output is correct
5 Correct 1166 ms 166856 KB Output is correct