Submission #106428

#	Time	Username	Problem	Language	Result	Execution time	Memory
106428		eriksuenderhauf	Alternating Current (BOI18_alternating)	C++11	100 / 100	169 ms	17172 KiB

alternating

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%lld", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%lld\n", (n))
#define pii pair<int, int>
#define pil pair<int, long long>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vil vector<pil>
#define vll vector<pll>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef cc_hash_table<int,int,hash<int>> ht;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 2e5 + 5;
const double eps = 1e-9;
int a[MAXN], vis[MAXN], cnt = 5;
char ans[MAXN];
vii adj[MAXN];
vi comp;
int n, m;

bool dfs(int u, int p) {
	if (u == p) 
		return 1;
	if (vis[u % n] == cnt)
		return 0;
	vis[u % n] = cnt;
	for (pii nx: adj[u]) {
		comp.pb(nx.se);
		if (dfs(nx.fi, p))
			return 1;
		comp.pop_back();
	}
	return 0;
}

bool ok(int cur) {
	vis[cur] = ++cnt;
	for (pii nx: adj[cur]) {
		if (nx.fi == cur-1) continue;
		comp.pb(nx.se);
		if (dfs(nx.fi, cur + n))
			return 1;
		comp.pop_back();
	}
	return 0;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 0; i < m; i++) {
		int l, r;
		scanf("%d %d", &l, &r);
		if (l > r) {
			a[l]++, a[n + 1]--;
			a[1]++, a[r + 1]--;
			l--, r += n;
			adj[l].pb({r, i});
			adj[l+n].pb({2*n, i});
		} else {
			a[l]++, a[r + 1]--;
			l--;
			adj[l].pb({r, i});
			adj[l+n].pb({r+n, i});
		}
		ans[i] = '1';
	}
	for (int i = 1; i <= n; i++) {
		a[i] += a[i - 1];
		if (a[i] == 1)
			return !printf("impossible\n");
	}
	for (int i = 1; i <= n; i++) {
		a[i] = max(0, min(1, a[i] - 2));
		if (!a[i]) continue;
		adj[i].pb({i - 1, -1});
		adj[i + n].pb({i - 1 + n, -1});
	}
	for (int i = 0; i < n; i++) {
		if (!ok(i)) continue;
		for (int j: comp)
			if (j != -1)
				ans[j] = '0';
		return !printf("%s\n", ans);
	}
	printf("impossible\n");
	return 0;
}

Compilation message (stderr)

alternating.cpp: In function 'int main()':
alternating.cpp:69: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:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &l, &r);
   ~~~~~^~~~~~~~~~~~~~~~~

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