oj.uz

Submission #476969

# Submission time Handle Problem Language Result Execution time Memory
476969 2021-09-29T13:52:12 Z AdamGS Teoretičar (COCI18_teoreticar) C++14
130 / 130
 6328 ms 168268 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
#define int long long
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7;
vector<pair<int,int>>V[LIM];
vector<int>cykl;
pair<int,int>T[LIM];
int ans[LIM], li[LIM], odw[LIM], ile[LIM], l, r, m;
bool ok(vector<int>kraw) {
	if(kraw.size()==0) return true;
	vector<int>wierz;
	for(auto i : kraw) {
		wierz.pb(T[i].st);
		wierz.pb(T[i].nd);
	}
	sort(all(wierz));
	rep(i, wierz.size()-1) if(wierz[i]==wierz[i+1]) return false;
	return true;
}
void DFS(int x) {
	while(li[x]<V[x].size()) {
		int a=V[x][li[x]].st, b=V[x][li[x]].nd;
		++li[x];
		if(odw[b]) continue;
		odw[b]=1;
		DFS(a);		
		cykl.pb(b);
	}
}
void dc(vector<int>kraw, int x) {
	if(ok(kraw)) return;
	vector<int>P, wierz, lewo, prawo;
	V[l+r].clear();
	V[l+r+1].clear();
	ile[l+r]=ile[l+r+1]=li[l+r]=li[l+r+1]=0;
	for(auto i : kraw) {
		V[T[i].st].clear();
		V[T[i].nd].clear();
		li[T[i].st]=ile[T[i].st]=0;
		li[T[i].nd]=ile[T[i].nd]=0;
		odw[i]=0;
		P.pb(T[i].st);
		P.pb(T[i].nd);
	}
	for(auto i : kraw) {
		V[T[i].st].pb({T[i].nd, i});
		V[T[i].nd].pb({T[i].st, i});
		++ile[T[i].st];
		++ile[T[i].nd];
	}
	sort(all(P));
	wierz.pb(P[0]);
	rep(i, P.size()-1) if(P[i]!=P[i+1]) wierz.pb(P[i+1]);
	for(auto i : wierz) if(ile[i]%2==1) {
		if(i<l) lewo.pb(i);
		else prawo.pb(i);
	}
	int akt=m;
	rep(i, lewo.size()) {
		V[lewo[i]].pb({l+r, akt});
		V[l+r].pb({lewo[i], akt});
		++akt;
	}
	rep(i, prawo.size()) {
		V[prawo[i]].pb({l+r+1, akt});
		V[l+r+1].pb({prawo[i], akt});
		++akt;
	}
	if(V[l+r].size()%2==1) {
		V[l+r].pb({l+r+1, akt});
		V[l+r+1].pb({l+r, akt});
		++akt;
	}
	if(lewo.size()%2==1) {
		V[lewo.back()].pb({prawo.back(), m});
		V[prawo.back()].pb({lewo.back(), m});
		lewo.pop_back();
		prawo.pop_back();
		++akt;
	}
	for(int i=m; i<akt; ++i) odw[i]=0;
	vector<int>V1, V2;
	for(auto i : wierz) {
		cykl.clear();
		DFS(i);
		rep(j, cykl.size()) if(cykl[j]<m) {
			if(j%2==0) V1.pb(cykl[j]);
			else V2.pb(cykl[j]);
		}
	}
	for(auto i : V1) ans[i]+=x;
	dc(V1, 2*x);
	dc(V2, 2*x);
}
int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> l >> r >> m;
	vector<int>kraw;
	rep(i, m) {
		cin >> T[i].st >> T[i].nd;
		--T[i].st; --T[i].nd;
		T[i].nd+=l;
		kraw.pb(i);
	}
	dc(kraw, 1);
	map<int,int>mp;
	vector<int>skal;
	rep(i, m) skal.pb(ans[i]);
	sort(all(skal));
	int akt=0;
	for(auto i : skal) if(!mp[i]) {
		++akt;
		mp[i]=akt;
	}
	cout << akt << '\n';
	rep(i, m) cout << mp[ans[i]] << '\n';
}

Compilation message

teoreticar.cpp: In function 'bool ok(std::vector<long long int>)':
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:23:2: note: in expansion of macro 'rep'
   23 |  rep(i, wierz.size()-1) if(wierz[i]==wierz[i+1]) return false;
      |  ^~~
teoreticar.cpp: In function 'void DFS(long long int)':
teoreticar.cpp:27:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |  while(li[x]<V[x].size()) {
      |        ~~~~~^~~~~~~~~~~~
teoreticar.cpp: In function 'void dc(std::vector<long long int>, long long int)':
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:59:2: note: in expansion of macro 'rep'
   59 |  rep(i, P.size()-1) if(P[i]!=P[i+1]) wierz.pb(P[i+1]);
      |  ^~~
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:65:2: note: in expansion of macro 'rep'
   65 |  rep(i, lewo.size()) {
      |  ^~~
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:70:2: note: in expansion of macro 'rep'
   70 |  rep(i, prawo.size()) {
      |  ^~~
teoreticar.cpp:5:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
teoreticar.cpp:92:3: note: in expansion of macro 'rep'
   92 |   rep(j, cykl.size()) if(cykl[j]<m) {
      |   ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23884 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 12 ms 23756 KB Output is correct
4 Correct 14 ms 23840 KB Output is correct
5 Correct 14 ms 23848 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23804 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct
3 Correct 13 ms 23796 KB Output is correct
4 Correct 12 ms 23756 KB Output is correct
5 Correct 12 ms 23836 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 25572 KB Output is correct
2 Correct 24 ms 25300 KB Output is correct
3 Correct 27 ms 25940 KB Output is correct
4 Correct 18 ms 24808 KB Output is correct
5 Correct 20 ms 24812 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 25424 KB Output is correct
2 Correct 24 ms 25316 KB Output is correct
3 Correct 25 ms 26040 KB Output is correct
4 Correct 19 ms 25068 KB Output is correct
5 Correct 17 ms 24576 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1046 ms 115996 KB Output is correct
2 Correct 5576 ms 163576 KB Output is correct
3 Correct 2169 ms 160904 KB Output is correct
4 Correct 950 ms 121724 KB Output is correct
5 Correct 1062 ms 100800 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 116000 KB Output is correct
2 Correct 2118 ms 157388 KB Output is correct
3 Correct 3546 ms 164660 KB Output is correct
4 Correct 959 ms 118652 KB Output is correct
5 Correct 296 ms 47380 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4155 ms 149852 KB Output is correct
2 Correct 4440 ms 163432 KB Output is correct
3 Correct 263 ms 45864 KB Output is correct
4 Correct 1728 ms 124104 KB Output is correct
5 Correct 281 ms 73336 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2417 ms 136184 KB Output is correct
2 Correct 5784 ms 168268 KB Output is correct
3 Correct 4110 ms 164680 KB Output is correct
4 Correct 1669 ms 133268 KB Output is correct
5 Correct 951 ms 122772 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2191 ms 114660 KB Output is correct
2 Correct 6328 ms 164256 KB Output is correct
3 Correct 4909 ms 167316 KB Output is correct
4 Correct 1705 ms 133376 KB Output is correct
5 Correct 1836 ms 122388 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2202 ms 114280 KB Output is correct
2 Correct 6254 ms 163900 KB Output is correct
3 Correct 3546 ms 166932 KB Output is correct
4 Correct 419 ms 50608 KB Output is correct
5 Correct 1815 ms 121440 KB Output is correct