oj.uz

Submission #204708

# Submission time Handle Problem Language Result Execution time Memory
204708 2020-02-26T18:17:57 Z arnold518 Teoretičar (COCI18_teoreticar) C++14
52 / 130
 3066 ms 262148 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 = 2e5;
const int MAXM = 3e5;

struct Edge
{
	int u, v, p;
	bool operator < (const Edge &q) const { return v<q.v; }
};

int A, B, M;
vector<Edge> E;

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

set<Edge> adj[MAXN+10];
vector<Edge> cir;
int ans[MAXM+10];

void dfs(int now, Edge bef)
{
	vector<Edge> V;
	for(auto it : adj[now]) V.push_back(it);
	for(auto it : V)
	{
		if(adj[now].find(it)==adj[now].end()) continue;
		adj[now].erase(it);
		adj[it.v].erase({it.v, it.u, it.p});
		dfs(it.v, it);
	}
	if(bef.p!=-2)
	{
		if(bef.v>=A+1) cir.push_back({bef.u, bef.v-A-1, bef.p});
		else cir.push_back({bef.v, bef.u-A-1, bef.p});
	}
}

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

	vector<int> acomp, bcomp;
	for(auto it : V)
	{
		acomp.push_back(it.u);
		bcomp.push_back(it.v);
		CA[it.u]++; CB[it.v]++;
	}
	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.p]=k;

		for(auto it : acomp) CA[it]=0;
		for(auto it : bcomp) CB[it]=0;
		
		k++; return;
	}

	int cnt=0;
	for(auto it : acomp) if(CA[it]%2) V.push_back({it, 0, -1}), cnt++;
	for(auto it : bcomp) if(CB[it]%2) V.push_back({0, it, -1});
	if(cnt%2) V.push_back({0, 0, -1});

	for(auto it : V)
	{
		adj[it.u].insert({it.u, it.v+A+1, it.p});
		adj[it.v+A+1].insert({it.v+A+1, it.u, it.p});
	}
	acomp.push_back(0);
	for(auto it : acomp) dfs(it, {-1, -1, -2});

	vector<Edge> L, R;
	for(i=0; i<cir.size(); i++)
	{
		if(cir[i].p!=-1)
		{
			if(i%2) L.push_back(cir[i]);
			else R.push_back(cir[i]);
		}
	}

	cir.clear();

	for(auto it : acomp) CA[it]=0;
	for(auto it : bcomp) CB[it]=0;
		
	solve(L, k);
	solve(R, k);
}

int main()
{
	int i, j;

	scanf("%d%d%d", &A, &B, &M);
	for(i=1; i<=M; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		E.push_back({u, v, i});
	}
	int ans2=1;
	solve(E, 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<Edge>&, int&)':
teoreticar.cpp:89: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:109:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teoreticar.cpp:111: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:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9596 KB Output is correct
3 Correct 11 ms 9852 KB Output is correct
4 Correct 11 ms 9724 KB Output is correct
5 Correct 12 ms 9848 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 9720 KB Output is correct
2 Correct 11 ms 9720 KB Output is correct
3 Correct 11 ms 9720 KB Output is correct
4 Correct 11 ms 9720 KB Output is correct
5 Correct 11 ms 9720 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 31184 KB Output is correct
2 Correct 86 ms 14444 KB Output is correct
3 Correct 248 ms 40824 KB Output is correct
4 Correct 18 ms 11128 KB Output is correct
5 Correct 17 ms 11128 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 24856 KB Output is correct
2 Correct 86 ms 14472 KB Output is correct
3 Correct 258 ms 45432 KB Output is correct
4 Correct 22 ms 11512 KB Output is correct
5 Correct 21 ms 11000 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 804 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 805 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3066 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2337 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2704 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 2716 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -