Submission #204813

#	Time	Username	Problem	Language	Result	Execution time	Memory
204813		arnold518	Teoretičar (COCI18_teoreticar)	C++14	52 / 130	2584 ms	24480 KiB

teoreticar

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;
const int MAXM = 5e5;

int A, B, M;
pii E[MAXN+10];

int CA[MAXN+10], CB[MAXN+10];

bool S[MAXM*2+10];
vector<pii> adj1[MAXN+10], adj2[MAXN+10];
vector<int> cir;
int ans[MAXM+10];

void dfs(int now, int edge, int col)
{
	if(col==1)
	{
		for(auto &nxt : adj1[now])
		{
			if(S[nxt.second]) continue;
			S[nxt.second]=1;
			dfs(nxt.first, nxt.second, 2);
		}
	}
	else
	{
		for(auto &nxt : adj2[now])
		{
			if(S[nxt.second]) continue;
			S[nxt.second]=1;
			dfs(nxt.first, nxt.second, 1);
		}
	}
	if(edge!=-2) cir.push_back(edge);
}

void solve(vector<int> &V, int &k)
{
	int i, j;

	vector<int> acomp, bcomp;
	for(auto &it : V)
	{
		acomp.push_back(E[it].first);
		bcomp.push_back(E[it].second);
		CA[E[it].first]++; CB[E[it].second]++;
	}
	sort(acomp.begin(), acomp.end());
	acomp.erase(unique(acomp.begin(), acomp.end()), acomp.end());

	sort(bcomp.begin(), bcomp.end());
	bcomp.erase(unique(bcomp.begin(), bcomp.end()), bcomp.end());

	int maxdeg=0;
	for(auto &it : acomp) maxdeg=max(maxdeg, CA[it]);
	for(auto &it : bcomp) maxdeg=max(maxdeg, CB[it]);

	if(maxdeg<=1)
	{
		for(auto &it : V) ans[it]=k;

		for(auto &it : acomp) CA[it]=0;
		for(auto &it : bcomp) CB[it]=0;
		
		vector<int>().swap(V);
		vector<int>().swap(acomp);
		vector<int>().swap(bcomp);
		k++; return;
	}

	for(auto &it : V)
	{
		adj1[E[it].first].push_back({E[it].second, it});
		adj2[E[it].second].push_back({E[it].first, it});
	}

	int cnt=0;
	int num=M+1;
	for(auto &it : acomp) if(CA[it]%2)
	{
		adj1[it].push_back({0, num});
		adj2[0].push_back({it, num});
		num++;
		cnt++;
	}
	for(auto &it : bcomp) if(CB[it]%2)
	{
		adj2[it].push_back({0, num});
		adj1[0].push_back({it, num});
		num++;
	}
	if(cnt%2)
	{
		adj1[0].push_back({0, num});
		adj2[0].push_back({0, num});
		num++;
	}

	acomp.push_back(0); bcomp.push_back(0);
	for(auto it : acomp) dfs(it, -2, 1);
	
	for(auto &it : V) S[it]=0;
	for(i=M+1; i<num; i++) S[i]=0;

	vector<int>().swap(V);

	for(auto &it : acomp) CA[it]=0;
	for(auto &it : bcomp) CB[it]=0;
	
	for(auto &it : acomp) vector<pii>().swap(adj1[it]);
	for(auto &it : bcomp) vector<pii>().swap(adj2[it]);

	vector<int>().swap(acomp);
	vector<int>().swap(bcomp);

	vector<int> L, R;
	for(i=0; i<cir.size(); i++)
	{
		if(cir[i]<=M)
		{
			if(i%2) L.push_back(cir[i]);
			else R.push_back(cir[i]);
		}
	}
	vector<int>().swap(cir);

	solve(L, k);
	solve(R, k);
}

int main()
{
	int i, j;

	scanf("%d%d%d", &A, &B, &M);
	for(i=1; i<=M; i++) scanf("%d%d", &E[i].first, &E[i].second);

	vector<int> V;
	for(i=1; i<=M; i++) V.push_back(i);
	int ans2=1;
	solve(V, ans2);

	printf("%d\n", ans2-1);
	for(i=1; i<=M; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

teoreticar.cpp: In function 'void solve(std::vector<int>&, int&)':
teoreticar.cpp:124:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<cir.size(); i++)
           ~^~~~~~~~~~~
teoreticar.cpp:46:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:140:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
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", &A, &B, &M);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:143:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%d%d", &E[i].first, &E[i].second);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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