Submission #419275

#	Time	Username	Problem	Language	Result	Execution time	Memory
419275		volkyoe	Alternating Current (BOI18_alternating)	C++17	100 / 100	126 ms	11388 KiB

alternating

#include"bits/stdc++.h"
using namespace std;
int N, M, x, y, Cnt[200005], D[100005];

int Two[100005], T, Vt[100005][2], V[100005];
vector<int> AdjList[100005];

int NT[100005], AC[100005], last[2];
pair<int, int> P[100005];

class Cmp {
	public:
		bool operator() (int i, int j) const {
			return P[i] < P[j];
		}
};
bool bipartite(int u) {
	queue<int> Q;
	Q.push(u);
	while (!Q.empty()) {
		u = Q.front(), Q.pop();
		for (int v : AdjList[u]) {
			if (!NT[v]) continue;
			if (AC[v] == AC[u]) return false;
			if (AC[v]) continue;	
			Q.push(v), AC[v] = -AC[u];
		}
	}
	return true;
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; i++) {
		scanf("%d%d", &x, &y);
		if (y < x) y += N;
		++Cnt[--x], --Cnt[y];
		P[i] = {x, y};
		D[i-1] = i;
	}
	
	for (int i = 1; i < 2*N; i++)
		Cnt[i] += Cnt[i-1];
	for (int i = 0; i < N; i++) {
		Cnt[i] += Cnt[i+N];
		//printf("Cnt[%d]: %d\n", i, Cnt[i]);
		if (Cnt[i] < 2) {
			printf("impossible");
			return 0;
		}
		if (Cnt[i] == 2) Two[T++] = i;
	}
	
	if (T > 0) {
		for (int i = 1; i <= M; i++) {
			tie(x, y) = P[i];
			int lb = (lower_bound(Two, Two + T, x) - Two) % T;
			int ub = (lower_bound(Two, Two + T, y % N) - Two) % T;
			//printf("(%d, %d) [%d, %d]\n", x, y, lb, ub);
			for (int j = lb; j != ub; j = (j + 1) % T)
				Vt[j][V[j]++] = i;
		}
		//for (int i = 0; i < T; i++) printf("[%d] %d %d\n", V[i], Vt[i][0], Vt[i][1]);
		
		for (int i = 0; i < T; i++) {
			AdjList[Vt[i][0]].push_back(Vt[i][1]);
			AdjList[Vt[i][1]].push_back(Vt[i][0]);
			NT[Vt[i][0]] = NT[Vt[i][1]] = 1;
		}
		//for (int i = 1; i <= M; i++) printf("%d ", NT[i]); printf("\n");
	}
	
	sort(D, D + M, Cmp());
	last[0] = last[1] = P[D[0]].first;
	for (int i = 0; i < M; i++) {
		int p = D[i];
		tie(x, y) = P[p];
		if (AC[p]) {
			int l = (AC[p] + 1) >> 1;
			last[l] = max(last[l], y);
			continue;
		}
		int l = last[0] < last[1] ? 0 : 1;
		AC[p] = l - !l;
		if (NT[p] && !bipartite(p)) {
			printf("impossible");
			return 0;
		}
		last[l] = max(last[l], y);
		//for (int m = 1; m <= M; m++) AC[m] ? printf("%d", (AC[m]+1) >> 1) : printf("-"); printf("\n");
	}
	
	for (int i = 1; i <= M; i++)
		printf("%d", 1 - ((AC[i] + 1) >> 1));
}
/*
12 4
1 9
4 12
7 3
10 6
*/

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
alternating.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26