Submission #1031882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031882		ten_xd	Teoretičar (COCI18_teoreticar)	C++17	130 / 130	3533 ms	204948 KiB

teoreticar

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back

const int N = 8e5+5, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;

struct Krawedz
{
	int a,b,idx;
};

struct Kraw
{
	int v,c;
};

int l,r,m,cnter,nr,kol,ro;
vector<Kraw> G[N];
int il[N];
bool uz[N];
bool vis[N];
int wyn[N];
bool vif[N];
vector<Krawedz> F[2];
vector<int> g[N];
vector<Krawedz> wie;

void DFS(int v)
{
	while(!G[v].empty())
	{
		Kraw akt = G[v].back();
		G[v].pop_back();
		if(vis[akt.c]) continue;
		vis[akt.c] = 1;
		DFS(akt.v);
		wie.pb({min(v,akt.v),max(v,akt.v),akt.c});
	}
}

int xn = 0;
void DFS2(int v)
{
	vif[v] = 1, ++xn;
	for(auto x : g[v]) if(!vif[x]) DFS2(x);
}

void rek(vector<Krawedz> E)
{
	if(E.empty()) return;

	int ok = 0;
	for(auto x : E) g[x.a].pb(x.b), g[x.b].pb(x.a);
	for(auto x : E)
	{
		if(vif[x.a]) continue;
		xn = 0;
		DFS2(x.a);
		if(xn == 2) ++ok;
	}
	for(auto x : E) g[x.a].clear(), g[x.b].clear(), vif[x.a] = 0, vif[x.b] = 0;
	if(ok == (int)E.size())
	{
		++cnter;
		for(auto x : E)
		{
			wyn[x.idx] = cnter;
		}
		return;
	}

	vector<int> V;
	for(auto x : E)
	{
		++il[x.a], ++il[x.b], V.pb(x.a), V.pb(x.b);
	}

	for(auto x : E) G[x.a].pb({x.b,x.idx}), G[x.b].pb({x.a,x.idx});
	nr = (int)m-1, ro = nr;

	for(auto x : V)
	{
		if(uz[x]) continue;
		uz[x] = 1;
		if(il[x] % 2 == 1) G[0].pb({x,++nr}), G[x].pb({0,nr});
	}

	rep(i,2) F[i].clear();
	for(int i = 0; i <= nr; ++i) vis[i] = 0;
	for(auto v : V)
	{
		//cout << '\n';
		wie.clear();
		DFS(v);
		if((int)wie.size() == 0) continue;
		int at = -1;
		if((int)wie.size() == 1) at = wie[0].a;
		else if(wie[0].a == wie[1].a or wie[0].a == wie[1].b) at = wie[0].b;
		else at = wie[0].a;
		for(int i = 0; i < (int)wie.size(); ++i)
		{
			int ko = 0;
			if(wie[i].a != at)
			{
				if(at < wie[i].a) ko = 1;
				if(at > 0 and wie[i].a > 0) F[ko].pb({at,wie[i].a,wie[i].idx});
				at = wie[i].a;
			}
			else
			{
				if(at < wie[i].b) ko = 1;
				if(at > 0 and wie[i].b > 0) F[ko].pb({at,wie[i].b,wie[i].idx});
				at = wie[i].b;
			}
		}
	}

	for(auto x : E) il[x.a] = 0, il[x.b] = 0, G[x.a].clear(), G[x.b].clear(), uz[x.a] = 0, uz[x.b] = 0;
	G[0].clear();

	vector<Krawedz> af = F[0], bf = F[1];
	rek(af);
	rek(bf);
}

void solve()
{
	cin >> l >> r >> m;
	vector<Krawedz> K;
	rep(i,m)
	{
		int a,b;
		cin >> a >> b;
		K.pb({a,l+b,i});
	}

	rek(K);

	int re = 1;
	for(int i = 1; i < cnter; i *= 2, re *= 2);
	cout << re << '\n';
	rep(i,m) cout << wyn[i] << '\n';
}

int main()
{	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T = 1;
	//cin >> T;
	while(T--) solve();

	return 0;
}

• 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