Submission #92014

#	Time	Username	Problem	Language	Result	Execution time	Memory
92014		jasony123123	Ili (COI17_ili)	C++11	100 / 100	2811 ms	2552 KiB

ili

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/****************************************************************/

const int MX = 20100;
int n, m;
int type[MX];
v<int> adj[MX], rev[MX];

void input() {
	cin >> n >> m;
	string s;
	cin >> s;
	FORE(i, 1, n) type[i] = -1;
	FORE(i, 1 + n, m + n) type[i] = ((s[i - 1 - n] == '?') ? -1 : (s[i - 1 - n] - '0'));
	FORE(i, 1 + n, m + n) {
		string x, y;
		cin >> x >> y;
		int xx = stoi(x.substr(1, x.size() - 1));
		int yy = stoi(y.substr(1, y.size() - 1));
		int a = (x[0] == 'x') ? (xx) : (xx + n);
		int b = (y[0] == 'x') ? (yy) : (yy + n);
		adj[i].push_back(a), adj[i].push_back(b);
		rev[a].push_back(i), rev[b].push_back(i);
	}
}

void check() {
	darr(type, n + m + 1);
	FORE(i, 1, n + m) {
		cout << i << ": ";
		for (int x : adj[i])
			cout << x << " ";
		cout << "\n";
	}
}

void fill0() {
	bool vis[MX];
	memset(vis, 0, sizeof vis);
	queue<int> q;
	FORE(i, 1, n + m) if (type[i] == 0) {
		q.push(i);
		vis[i] = 1;
	}
	while (!q.empty()) {
		int x = q.front();
		type[x] = 0;
		q.pop();
		for (auto i : adj[x]) if (!vis[i]) {
			q.push(i);
			vis[i] = 1;
		}
	}
}


bool vis0[MX];
bool is0(int a) {
	// can not be 1: T-not vis   F-vis
	return !vis0[a];
}

void init() {
	queue<int> q;
	FORE(i, 1, n) if (type[i] == -1) {
		q.push(i);
		vis0[i] = 1;
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto i : rev[x]) if (!vis0[i]) {
			q.push(i);
			vis0[i] = 1;
		}
	}
}

bool is1(int a) {
	// can not be 0
	int tmptyp[MX];
	FORE(i, 1, n + m) tmptyp[i] = type[i];

	bool vis[MX];
	memset(vis, 0, sizeof vis);
	queue<int> q;
	q.push(a);
	while (!q.empty()) {
		int x = q.front();
		tmptyp[x] = 0;
		q.pop();
		for (auto i : adj[x]) if (!vis[i]) {
			q.push(i);
			vis[i] = 1;
		}
	}

	memset(vis, 0, sizeof vis);
	FORE(i, 1, n) if (tmptyp[i] == -1) {
		q.push(i);
		vis[i] = 1;
	}
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (auto i : rev[x]) if (!vis[i]) {
			q.push(i);
			vis[i] = 1;
		}
	}

	// vis - reachable by 1
	FORE(i, 1, n + m) if (type[i] == 1)
		if (vis[i] == false) return true;
	return false;
}

int main() {
	io();
	input();
	fill0();
	//	check();
	init();
	string ans;
	RFORE(i, m + n, 1 + n) {
		if (type[i] != -1) ans += to_string(type[i]);
		else if (is0(i)) {
			ans += '0';
			type[i] = 0;
		}
		else if (is1(i)) {
			ans += '1';
			type[i] = 1;
		}
		else {
			ans += '?';
		}
	}
	reverse(all(ans));
	cout << ans;
	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 42 / 42
• Subtask 3: 51 / 51