Submission #86823

#	Time	Username	Problem	Language	Result	Execution time	Memory
86823		gs14004	Teoretičar (COCI18_teoreticar)	C++17	130 / 130	7238 ms	191060 KiB

teoreticar

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 500005;

int deg[MAXN], rem[MAXN], ptr[MAXN];
vector<pi> gph[MAXN];

int n, m, cnt, ret[MAXN];
pi a[MAXN];

void flush(vector<int> &V, vector<int> &E){
	for(auto &i : V){
		deg[i] = ptr[i] = 0;
		gph[i].clear();
	}
	for(auto &i : E) rem[i] = 0;
}

void dfs(int x, int c, vector<int> &l, vector<int> &r){
	while(ptr[x] < gph[x].size()){
		auto e = gph[x][ptr[x]];
		ptr[x]++;
		if(!rem[e.first]){
			rem[e.first] = 1;
			if(c & 1) r.push_back(e.first);
			else l.push_back(e.first);
			deg[a[e.first].first]--;
			deg[a[e.first].second]--;
			dfs(e.second, c + 1, l, r);
			break;
		}
	}
}

void assign(vector<int> edges){
	bool not_base = 0;
	vector<int> vlist;
	for(auto &i : edges){
		int s = a[i].first;
		int e = a[i].second;
		if(!deg[s]) vlist.push_back(s);
		deg[s]++;
		if(!deg[e]) vlist.push_back(e);
		deg[e]++;
		if(deg[s] > 1 || deg[e] > 1) not_base = 1;
		gph[s].emplace_back(i, e);
		gph[e].emplace_back(i, s);
	}
	if(!not_base){
		cnt++;
		for(auto &i : edges) ret[i] = cnt;
		flush(vlist, edges);
		return;
	}
	vector<int> l, r;
	for(auto &i : vlist){
		if(deg[i] & 1){
			dfs(i, 0, l, r);
		}
	}
	for(auto &i : vlist){
		while(deg[i]){
			dfs(i, 0, l, r);
		}
	}
	flush(vlist, edges);
	assign(l);
	assign(r);
}

int main(){
	int k;
	scanf("%d %d %d",&n,&k,&m);
	vector<int> v;
	for(int i=0; i<m; i++){
		scanf("%d %d",&a[i].first,&a[i].second);
		a[i].second += n;
		v.push_back(i);
	}
	assign(v);
	printf("%d\n", cnt);
	for(int i=0; i<m; i++){
		printf("%d\n", ret[i]);
	}
}

Compilation message (stderr)

teoreticar.cpp: In function 'void dfs(int, int, std::vector<int>&, std::vector<int>&)':
teoreticar.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr[x] < gph[x].size()){
        ~~~~~~~^~~~~~~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&k,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first,&a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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