oj.uz

Submission #86823

# Submission time Handle Problem Language Result Execution time Memory
86823 2018-11-27T16:10:28 Z gs14004 Teoretičar (COCI18_teoreticar) C++17
130 / 130
 7238 ms 191060 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int MAXN = 500005;

int deg[MAXN], rem[MAXN], ptr[MAXN];
vector<pi> gph[MAXN];

int n, m, cnt, ret[MAXN];
pi a[MAXN];

void flush(vector<int> &V, vector<int> &E){
	for(auto &i : V){
		deg[i] = ptr[i] = 0;
		gph[i].clear();
	}
	for(auto &i : E) rem[i] = 0;
}

void dfs(int x, int c, vector<int> &l, vector<int> &r){
	while(ptr[x] < gph[x].size()){
		auto e = gph[x][ptr[x]];
		ptr[x]++;
		if(!rem[e.first]){
			rem[e.first] = 1;
			if(c & 1) r.push_back(e.first);
			else l.push_back(e.first);
			deg[a[e.first].first]--;
			deg[a[e.first].second]--;
			dfs(e.second, c + 1, l, r);
			break;
		}
	}
}

void assign(vector<int> edges){
	bool not_base = 0;
	vector<int> vlist;
	for(auto &i : edges){
		int s = a[i].first;
		int e = a[i].second;
		if(!deg[s]) vlist.push_back(s);
		deg[s]++;
		if(!deg[e]) vlist.push_back(e);
		deg[e]++;
		if(deg[s] > 1 || deg[e] > 1) not_base = 1;
		gph[s].emplace_back(i, e);
		gph[e].emplace_back(i, s);
	}
	if(!not_base){
		cnt++;
		for(auto &i : edges) ret[i] = cnt;
		flush(vlist, edges);
		return;
	}
	vector<int> l, r;
	for(auto &i : vlist){
		if(deg[i] & 1){
			dfs(i, 0, l, r);
		}
	}
	for(auto &i : vlist){
		while(deg[i]){
			dfs(i, 0, l, r);
		}
	}
	flush(vlist, edges);
	assign(l);
	assign(r);
}

int main(){
	int k;
	scanf("%d %d %d",&n,&k,&m);
	vector<int> v;
	for(int i=0; i<m; i++){
		scanf("%d %d",&a[i].first,&a[i].second);
		a[i].second += n;
		v.push_back(i);
	}
	assign(v);
	printf("%d\n", cnt);
	for(int i=0; i<m; i++){
		printf("%d\n", ret[i]);
	}
}

Compilation message

teoreticar.cpp: In function 'void dfs(int, int, std::vector<int>&, std::vector<int>&)':
teoreticar.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ptr[x] < gph[x].size()){
        ~~~~~~~^~~~~~~~~~~~~~~
teoreticar.cpp: In function 'int main()':
teoreticar.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&k,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
teoreticar.cpp:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].first,&a[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 14 ms 12280 KB Output is correct
3 Correct 12 ms 12280 KB Output is correct
4 Correct 15 ms 12288 KB Output is correct
5 Correct 12 ms 12368 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12412 KB Output is correct
2 Correct 12 ms 12420 KB Output is correct
3 Correct 12 ms 12424 KB Output is correct
4 Correct 11 ms 12428 KB Output is correct
5 Correct 11 ms 12428 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12956 KB Output is correct
2 Correct 21 ms 13020 KB Output is correct
3 Correct 20 ms 13240 KB Output is correct
4 Correct 14 ms 13240 KB Output is correct
5 Correct 15 ms 13240 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 13240 KB Output is correct
2 Correct 18 ms 13240 KB Output is correct
3 Correct 18 ms 13480 KB Output is correct
4 Correct 19 ms 13480 KB Output is correct
5 Correct 16 ms 13480 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 43440 KB Output is correct
2 Correct 6302 ms 72164 KB Output is correct
3 Correct 1729 ms 72164 KB Output is correct
4 Correct 809 ms 77888 KB Output is correct
5 Correct 474 ms 77888 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 77888 KB Output is correct
2 Correct 1972 ms 83764 KB Output is correct
3 Correct 2899 ms 94508 KB Output is correct
4 Correct 982 ms 98088 KB Output is correct
5 Correct 135 ms 98088 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2029 ms 98088 KB Output is correct
2 Correct 3722 ms 110676 KB Output is correct
3 Correct 98 ms 110676 KB Output is correct
4 Correct 1000 ms 122228 KB Output is correct
5 Correct 236 ms 122228 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1262 ms 138028 KB Output is correct
2 Correct 6482 ms 138028 KB Output is correct
3 Correct 3504 ms 138028 KB Output is correct
4 Correct 952 ms 148120 KB Output is correct
5 Correct 986 ms 148120 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 148120 KB Output is correct
2 Correct 7238 ms 162112 KB Output is correct
3 Correct 4800 ms 162112 KB Output is correct
4 Correct 957 ms 172356 KB Output is correct
5 Correct 843 ms 172428 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 172428 KB Output is correct
2 Correct 6902 ms 185376 KB Output is correct
3 Correct 3661 ms 185376 KB Output is correct
4 Correct 162 ms 185376 KB Output is correct
5 Correct 899 ms 191060 KB Output is correct