제출 #1320023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1320023		NikoBaotic	Ili (COI17_ili)	C++20	100 / 100	585 ms	99072 KiB

ili

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define pb push_back
#define F first
#define S second
#define FIO ios_base::sync_with_stdio(false); cin.tie(0)

const int N = 1e4 + 10;
const int M = 1e4 + 10;

int n, m;

string s;
pii d0[M];
pii d1[M];

vector<int> d[M];

bool rem[N];
bool has[M];
bool temp[N];

void dfs(int node, int par) {
	if (d0[node].S) d[par].pb(d0[node].F);
	else dfs(d0[node].F, par);
	
	if (d1[node].S) d[par].pb(d1[node].F);
	else dfs(d1[node].F, par);
}

int main() {
	FIO;
	
	cin >> n >> m;

	cin >> s;

	for (int i = 1; i <= m; i++) {
		string a, b;
		cin >> a >> b;

		d0[i].S = a[0] == 'x';
		d1[i].S = b[0] == 'x';

		a.erase(a.begin());
		b.erase(b.begin());

		d0[i].F = stoi(a);
		d1[i].F = stoi(b);
	}

	for (int i = 1; i <= m; i++) {
		dfs(i, i);
	}

	for (int i = 1; i <= m; i++) {
		if (s[i - 1] == '0') {
			for (int x : d[i]) {
				rem[x] = 1;
			}
		}
	}

	for (int i = 1; i <= m; i++) {
		int cnt = 0;

		for (int x : d[i]) {
			if (!rem[x]) cnt++;
		}

		if (cnt == 0) {
			s[i - 1] = '0';
			continue;
		}

		for (int x : d[i]) {
			if (!rem[x]) {
				temp[x] = 1;
				rem[x] = 1;
			}
		}

		memset(has, 0, sizeof has);

		bool valid = 1;

		for (int j = 1; j <= m; j++) {
			bool cur = 0;

			if (d0[j].S) {
				if (!rem[d0[j].F]) cur = 1;
			} else {
				if (has[d0[j].F]) cur = 1;
			}
			
			if (d1[j].S) {
				if (!rem[d1[j].F]) cur = 1;
			} else {
				if (has[d1[j].F]) cur = 1;
			}
			
			has[j] = cur;

			if (!has[j] and s[j - 1] == '1') valid = 0;
		}

		for (int x : d[i]) {
			if (temp[x]) {
				rem[x] = 0;
				temp[x] = 1;
			}
		}

		if (valid) {
			s[i - 1] = '?';
		} else {
			s[i - 1] = '1';
		}
	}

	cout << s << endl;

	return 0;
}

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