oj.uz

Submission #63212

# Submission time Handle Problem Language Result Execution time Memory
63212 2018-08-01T06:04:21 Z 김세빈(#1833) Alternating Current (BOI18_alternating) C++11
0 / 100
 125 ms 17688 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair <int, int> pii;

vector <int> L[101010], V[101010];
vector <int> X[101010], Y[101010];
set <int> S;
pii P[101010];
int chk[101010], ans[101010];
int fff[101010];
int n, m;

void die() { printf("impossible\n"); exit(0); }

void dfs(int p, int c)
{
	chk[p] = 2; ans[p] = c;
	for(int &t: V[p]){
		if(chk[t] == 1) dfs(t, !c);
		else if(ans[t] == ans[p]) die();
	}
}

int main()
{
	int i, s, e, x, y, a, b;
	
	scanf("%d%d", &n, &m);
	
	for(i=1; i<=m; i++){
		scanf("%d%d", &a, &b);
		b ++; if(b > n) b -= n;
		P[i] = pii(a, b);
		if(a < b){
			L[a].push_back(i);
			L[b].push_back(-i);
		}
		else{
			L[1].push_back(i);
			L[b].push_back(-i);
			L[a].push_back(i);
		}
	}
	
	for(i=1; i<=n; i++){
		for(int &t: L[i]){
			if(t > 0) S.insert(t);
			else S.erase(-t);
		}
		
		if(S.size() == 2){
			a = *S.begin(); b = *next(S.begin());
			V[a].push_back(b);
			V[b].push_back(a);
			chk[a] = 1; chk[b] = 1;
		}
		else if(S.size() == 1) die();
	}
	
	for(i=1; i<=m; i++){
		if(chk[i] == 1) dfs(i, 0);
	}
	
	x = 1;
	
	for(i=1; i<=m; i++){
		if(chk[i]){
			if(ans[i] == 1){
				X[P[i].first].push_back(i);
				x = i;
			}
		}
		else Y[P[i].first].push_back(i);
	}
	
	ans[x] = 1; y = -1;
	s = P[x].first, e = P[x].second;
	
	for(i=s; ; ){
		for(int &t: X[i]){
			if(P[t].first < P[t].second){
				if(i <= e && e < P[t].second) e = P[t].second;
			}
			else{
				if(i <= e) e = P[t].second;
				else if(e < P[t].second) e = P[t].second;
			}
		}
		for(int &t: Y[i]){
			if(y == -1) y = t;
			else if(P[t].first < P[t].second){
				if(i <= P[y].second && P[y].second < P[t].second) y = t;
			}
			else{
				if(i <= P[y].second) y = t;
				else if(P[y].second < P[t].second) y = t;
			}
		}
		
		if(i == e){
			if(y == -1) die();
			ans[y] = 1; y = -1;
			e = P[y].second;
			i = P[y].first;
		}
		
		i ++; if(i > n) i -= n;
		if(i == s) break;
	}
	
	for(i=1; i<=m; i++) printf("%d", ans[i]);
	printf("\n");
	
	return 0;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:105:11: warning: array subscript is below array bounds [-Warray-bounds]
    e = P[y].second;
        ~~~^
alternating.cpp:106:11: warning: array subscript is below array bounds [-Warray-bounds]
    i = P[y].first;
        ~~~^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Incorrect 13 ms 9828 KB 'impossible' claimed, but there is a solution
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Incorrect 13 ms 9828 KB 'impossible' claimed, but there is a solution
3 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Incorrect 13 ms 9828 KB 'impossible' claimed, but there is a solution
3 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 17688 KB Output is correct
2 Incorrect 16 ms 17688 KB 'impossible' claimed, but there is a solution
3 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 9720 KB Output is correct
2 Incorrect 13 ms 9828 KB 'impossible' claimed, but there is a solution
3 Halted 0 ms 0 KB -