oj.uz

Submission #92014

# Submission time Handle Problem Language Result Execution time Memory
92014 2019-01-01T02:31:15 Z jasony123123 Ili (COI17_ili) C++11
100 / 100
 2811 ms 2552 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 2 ms 1272 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 9 ms 1272 KB Output is correct
5 Correct 2 ms 1272 KB Output is correct
6 Correct 3 ms 1404 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 2 ms 1272 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 9 ms 1272 KB Output is correct
5 Correct 2 ms 1272 KB Output is correct
6 Correct 3 ms 1404 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct
8 Correct 5 ms 1400 KB Output is correct
9 Correct 4 ms 1272 KB Output is correct
10 Correct 4 ms 1400 KB Output is correct
11 Correct 5 ms 1400 KB Output is correct
12 Correct 4 ms 1400 KB Output is correct
13 Correct 13 ms 1400 KB Output is correct
14 Correct 6 ms 1400 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 2 ms 1272 KB Output is correct
3 Correct 3 ms 1400 KB Output is correct
4 Correct 9 ms 1272 KB Output is correct
5 Correct 2 ms 1272 KB Output is correct
6 Correct 3 ms 1404 KB Output is correct
7 Correct 3 ms 1400 KB Output is correct
8 Correct 5 ms 1400 KB Output is correct
9 Correct 4 ms 1272 KB Output is correct
10 Correct 4 ms 1400 KB Output is correct
11 Correct 5 ms 1400 KB Output is correct
12 Correct 4 ms 1400 KB Output is correct
13 Correct 13 ms 1400 KB Output is correct
14 Correct 6 ms 1400 KB Output is correct
15 Correct 437 ms 1884 KB Output is correct
16 Correct 984 ms 2168 KB Output is correct
17 Correct 696 ms 2084 KB Output is correct
18 Correct 2692 ms 2424 KB Output is correct
19 Correct 733 ms 2044 KB Output is correct
20 Correct 1975 ms 2424 KB Output is correct
21 Correct 2811 ms 2552 KB Output is correct
22 Correct 515 ms 2400 KB Output is correct
23 Correct 526 ms 2552 KB Output is correct
24 Correct 537 ms 2424 KB Output is correct
25 Correct 407 ms 2140 KB Output is correct
26 Correct 428 ms 2040 KB Output is correct
27 Correct 414 ms 2140 KB Output is correct
28 Correct 405 ms 2040 KB Output is correct
29 Correct 408 ms 2100 KB Output is correct
30 Correct 390 ms 2040 KB Output is correct
31 Correct 345 ms 2168 KB Output is correct
32 Correct 438 ms 2296 KB Output is correct