제출 #1031534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031534		ten_xd	Teoretičar (COCI18_teoreticar)	C++17	0 / 130	365 ms	129200 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 = 5e5+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];

void DFS(int v)
{
	while(!G[v].empty())
	{
		Kraw akt = G[v].back();
		G[v].pop_back();
		//cout << "V: " << v << " AKT V: " << akt.v << " AKT C: " << akt.c << '\n';
		if(vis[akt.c]) continue;
		vis[akt.c] = 1;
		DFS(akt.v);
		if(akt.c <= ro)
		{
			int ko = 0;
			if(v < akt.v) ko = 1;
			F[ko].pb({v,akt.v,akt.c});
		}
		//cout << "V: " << v << " AKT: " << akt.v << " C: " << akt.c << " KOL: " << kol << '\n';
	}
}

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;

	//cout << '\n';
	//cout << "EDGES: " << '\n';
	//for(auto x : E) cout << "A: " << x.a << " B: " << x.b << " IDX: " << x.idx << '\n';
	//cout << '\n';

	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)
		{
			//cout << "IDXXXX: " << x.idx << " CNTER: " << cnter << '\n';
			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)E.size()-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';
		DFS(v);
		//cout << '\n';
	}

	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);

	//cout << "CNTER: " << cnter << '\n';

	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: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 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