oj.uz

Submission #204825

# Submission time Handle Problem Language Result Execution time Memory
204825 2020-02-27T10:13:16 Z arnold518 Teoretičar (COCI18_teoreticar) C++14
130 / 130
 6948 ms 48856 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 1e5;
const int MAXM = 5e5;
 
int A, B, M;
pii E[MAXM+10];
 
int CA[MAXN+10], CB[MAXN+10];
 
bool S[MAXM*2+10], T[MAXN+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)
	{
		T[now]=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 euler(int now)
{
	vector<pair<int, pii>> ST;
	ST.push_back({now, {-2, 1}});
	while(!ST.empty())
	{
		int now=ST.back().first, edge=ST.back().second.first, col=ST.back().second.second;
		if(col==1)
		{
			T[now]=1;
			while(!adj1[now].empty() && S[adj1[now].back().second]) adj1[now].pop_back();
			if(!adj1[now].empty())
			{
				pii nxt=adj1[now].back();
				S[nxt.second]=1;
				ST.push_back({nxt.first, {nxt.second, 2}});
			}
			else
			{
				if(edge!=-2) cir.push_back(edge);
				ST.pop_back();
			}
		}
		else
		{
			while(!adj2[now].empty() && S[adj2[now].back().second]) adj2[now].pop_back();
			if(!adj2[now].empty())
			{
				pii nxt=adj2[now].back();
				S[nxt.second]=1;
				ST.push_back({nxt.first, {nxt.second, 1}});
			}
			else
			{
				if(edge!=-2) cir.push_back(edge);
				ST.pop_back();
			}
		}
	}
}
 
void solve(vector<int> &V, int &k)
{
	int i, j;
 
	vector<int> acomp, bcomp;
	for(auto &it : V)
	{
		if(!CA[E[it].first]) acomp.push_back(E[it].first);
		if(!CB[E[it].second]) bcomp.push_back(E[it].second);
		CA[E[it].first]++; CB[E[it].second]++;
	}

	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});
		CA[it]++; CB[0]++; num++; cnt++;
	}
	for(auto &it : bcomp) if(CB[it]%2)
	{
		adj2[it].push_back({0, num});
		adj1[0].push_back({it, num});
		CB[it]++; CA[0]++; num++;
	}
	if(cnt%2)
	{
		adj1[0].push_back({0, num});
		adj2[0].push_back({0, num});
		CA[0]++; CB[0]++; num++;
	}
 
	acomp.push_back(0); bcomp.push_back(0);
	for(auto it : acomp) if(!T[it]) euler(it);
	
	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) T[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

teoreticar.cpp: In function 'void solve(std::vector<int>&, int&)':
teoreticar.cpp:161:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0; i<cir.size(); i++)
           ~^~~~~~~~~~~
teoreticar.cpp:88:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:177:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teoreticar.cpp:179: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:180: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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4984 KB Output is correct
2 Correct 8 ms 5116 KB Output is correct
3 Correct 8 ms 4984 KB Output is correct
4 Correct 9 ms 4984 KB Output is correct
5 Correct 8 ms 4984 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5624 KB Output is correct
2 Correct 16 ms 5496 KB Output is correct
3 Correct 20 ms 5752 KB Output is correct
4 Correct 11 ms 5288 KB Output is correct
5 Correct 12 ms 5368 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5496 KB Output is correct
2 Correct 17 ms 5496 KB Output is correct
3 Correct 22 ms 5752 KB Output is correct
4 Correct 13 ms 5368 KB Output is correct
5 Correct 13 ms 5240 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 887 ms 29528 KB Output is correct
2 Correct 5271 ms 43252 KB Output is correct
3 Correct 1867 ms 48084 KB Output is correct
4 Correct 801 ms 36180 KB Output is correct
5 Correct 562 ms 26976 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 872 ms 29652 KB Output is correct
2 Correct 1873 ms 42260 KB Output is correct
3 Correct 2912 ms 47956 KB Output is correct
4 Correct 817 ms 36140 KB Output is correct
5 Correct 154 ms 11368 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3596 ms 39000 KB Output is correct
2 Correct 3836 ms 48816 KB Output is correct
3 Correct 177 ms 11660 KB Output is correct
4 Correct 908 ms 32216 KB Output is correct
5 Correct 165 ms 22092 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 32856 KB Output is correct
2 Correct 5593 ms 42968 KB Output is correct
3 Correct 3386 ms 47572 KB Output is correct
4 Correct 987 ms 36204 KB Output is correct
5 Correct 782 ms 36052 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1334 ms 26328 KB Output is correct
2 Correct 6091 ms 42844 KB Output is correct
3 Correct 4720 ms 48856 KB Output is correct
4 Correct 1074 ms 36056 KB Output is correct
5 Correct 992 ms 31572 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1467 ms 26324 KB Output is correct
2 Correct 6948 ms 42700 KB Output is correct
3 Correct 3255 ms 48732 KB Output is correct
4 Correct 225 ms 12116 KB Output is correct
5 Correct 1030 ms 31340 KB Output is correct