Submission #361664

#	Time	Username	Problem	Language	Result	Execution time	Memory
361664		cmwqfcmwqf	Teoretičar (COCI18_teoreticar)	C++14	104 / 130	2788 ms	262144 KiB

teoreticar

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

#define pii pair<int, int>

const int maxN = 5e5 + 10;

struct Node
{
	int to, next;
}edge[maxN * 5 + 1];

int L, R, M, n, cnt, col;
int tot, head[maxN + 1];
int tl[maxN + 1], tr[maxN + 1];
int dl[maxN + 1], dr[maxN + 1];
int ans[maxN + 1], stk[maxN * 5 + 1], top;
bool vis[maxN * 5 + 1];

vector<pii> E[maxN * 2 + 1];
vector<int> vl[maxN * 2 + 1], vr[maxN * 2 + 1];

map<pii, int> G;

inline void clear(int node)
{
	for(int i = 2; i <= tot; i++) vis[i] = false;
	for(int i = 0; i < vl[node].size(); i++) 
	{
		int x = vl[node][i];
		dl[x] = head[x] = 0;
	}
	for(int i = 0; i < vr[node].size(); i++)
	{
		int x = vr[node][i] + n;
		dr[x - n] = head[x] = 0;
	}
	head[2 * n + 1] = head[2 * n + 2] = 0;
	tot = 1;
}

inline void add(int x, int y)
{
	edge[++ tot] = (Node){y, head[x]}; head[x] = tot;
	edge[++ tot] = (Node){x, head[y]}; head[y] = tot;
}

inline void dfs(int u)
{
	for(int &i = head[u]; i; i = edge[i].next)
	{
		if(vis[i]) continue;
		vis[i] = vis[i ^ 1] = true;
		dfs(edge[i].to);
	}
	stk[++ top] = u;
}

inline void solve(int node)
{
	for(int i = 0; i < E[node].size(); i++)
	{
		int u = E[node][i].first, v = E[node][i].second;
		add(u, v + n);
		dl[u] ++, dr[v] ++;
	}
	bool flag = true;
	for(int i = 0; i < vl[node].size(); i++)
		if(dl[ vl[node][i] ] > 1) { flag = false; break; }
	for(int i = 0; i < vr[node].size(); i++)
		if(dr[ vr[node][i] ] > 1) { flag = false; break; }
	if(flag)
	{
		col ++;
		for(int i = 0; i < E[node].size(); i++) ans[ G[ E[node][i] ] ] = col;
		clear(node);
		return;
	};
	int d1 = 0, d2 = 0;
	for(int i = 0; i < vl[node].size(); i++)	
		if(dl[ vl[node][i] ] & 1) add(vl[node][i], 2 * n + 2), d2 ++;
	for(int i = 0; i < vr[node].size(); i++)
		if(dr[ vr[node][i] ] & 1) add(2 * n + 1, vr[node][i] + n), d1 ++;
	if(d1 & 1) add(2 * n + 1, 2 * n + 2);
	int nl = ++ cnt, nr = ++ cnt;
	for(int i = 0; i < vl[node].size(); i++)
	{
		top = 0;
		dfs(vl[node][i]);
		while(top > 1)
		{
			int u = stk[top], v = stk[top - 1];
			top --;
			if(u > 2 * n || v > 2 * n) continue;
			if(u > n) swap(u, v);
			v -= n;
			if(top & 1) E[nl].push_back( pii(u, v) );
			else E[nr].push_back( pii(u, v) );
		}
	}
	clear(node);
	for(int i = 0; i < E[nl].size(); i++)
		tl[ E[nl][i].first ] = tr[ E[nl][i].second ] = nl;
	for(int i = 0; i < vl[node].size(); i++)
		if(tl[ vl[node][i] ] == nl) vl[nl].push_back(vl[node][i]);
	for(int i = 0; i < vr[node].size(); i++)
		if(tr[ vr[node][i] ] == nl) vr[nl].push_back(vr[node][i]);
	for(int i = 0; i < E[nr].size(); i++)
		tl[ E[nr][i].first ] = tr[ E[nr][i].second ] = nr;
	for(int i = 0; i < vl[node].size(); i++)
		if(tl[ vl[node][i] ] == nr) vl[nr].push_back(vl[node][i]);
	for(int i = 0; i < vr[node].size(); i++)
		if(tr[ vr[node][i] ] == nr) vr[nr].push_back(vr[node][i]);
	solve(nl), solve(nr);
}

int main()
{
	scanf("%d %d %d", &L, &R, &M);
	n = max(L, R);
	cnt ++;
	for(int i = 1; i <= M; i++)
	{
		int x, y;
		scanf("%d %d", &x, &y);
		G[ pii(x, y) ] = i;
		E[cnt].push_back( pii(x, y) );
		dl[x] ++, dr[y] ++;
	}
	for(int i = 1; i <= L; i++)
		if(dl[i]) vl[cnt].push_back(i);
	for(int i = 1; i <= R; i++)
		if(dr[i]) vr[cnt].push_back(i);
	for(int i = 1; i <= L; i++) dl[i] = 0;
	for(int i = 1; i <= R; i++) dr[i] = 0;
	tot = 1;

	solve(1);

	printf("%d\n", col);
	for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message (stderr)

teoreticar.cpp: In function 'void clear(int)':
teoreticar.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i = 0; i < vl[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < vr[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp: In function 'void solve(int)':
teoreticar.cpp:61:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i = 0; i < E[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~
teoreticar.cpp:68:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(int i = 0; i < vl[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < vr[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for(int i = 0; i < E[node].size(); i++) ans[ G[ E[node][i] ] ] = col;
      |                  ~~^~~~~~~~~~~~~~~~
teoreticar.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0; i < vl[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:82:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |  for(int i = 0; i < vr[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |  for(int i = 0; i < vl[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = 0; i < E[nl].size(); i++)
      |                 ~~^~~~~~~~~~~~~~
teoreticar.cpp:104:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for(int i = 0; i < vl[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:106:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i = 0; i < vr[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:108:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for(int i = 0; i < E[nr].size(); i++)
      |                 ~~^~~~~~~~~~~~~~
teoreticar.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |  for(int i = 0; i < vl[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp:112:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for(int i = 0; i < vr[node].size(); i++)
      |                 ~~^~~~~~~~~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |  scanf("%d %d %d", &L, &R, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  125 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• 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: 0 / 13
• Subtask 10: 0 / 13