Submission #377609

#	Time	Username	Problem	Language	Result	Execution time	Memory
377609		negar_a	Ili (COI17_ili)	C++14	7 / 100	26 ms	32364 KiB

ili

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 1e4 + 2;
int stat[maxn][5];
pii a[maxn], b[maxn];
vector <pii> adj[maxn][5][5][5], out[maxn][5];
vector <pii> vec;
vector < pair<pii, int>> pai[maxn][5];
bool mark[maxn][5], mrk[maxn][5][5];

void st(pii* x, char c, int u){
	u --;
	if(c == 'x'){
		*x = {1, u};
	}
	else{
		*x = {0, u};
	}
	return;
}

void dfs2(int u, int t, int x){
	mrk[u][t][x] = true;
	if(mrk[u][t][!x]){
		stat[u][t] = 1;
		vec.pb({u, t});
	}
	for(auto v : out[u][t]){
		if(!mrk[v.S][v.F][x]){
			dfs2(v.S, v.F, x);
		}
	}
}

void make(pii x, pii y){
	memset(mrk, 0, sizeof mrk);
	vec.clear();
	dfs2(x.S, x.F, 0);
	dfs2(y.S, y.F, 1);
}

void dfs(int u, int t){
//	cout << "ver : " << u << " | " << t << " s: " << stat[u][t] << endl;
	mark[u][t] = true;
	if(stat[u][t] == 0){
		for(auto v : pai[u][t]){
			if(stat[v.F.S][v.F.F] == 0 && !mark[v.S][0]){
				stat[v.S][0] = 0;
				dfs(v.S, 0);
			}
		}
	}
	if(t == 0 && stat[u][t] == 1){
		make(a[u], b[u]);
		adj[a[u].S][a[u].F][0][1].pb(b[u]);
		adj[b[u].S][b[u].F][0][1].pb(a[u]);
		for(auto v : vec){
			if(!mark[v.F][v.S]){
				dfs(v.F, v.S);
			}
		}
	}
	for(auto v : adj[u][t][stat[u][t]][0]){
		if(!mark[v.S][v.F]){
			stat[v.S][v.F] = 0;
			dfs(v.S, v.F);
		}
	}
	for(auto v : adj[u][t][stat[u][t]][1]){
		if(!mark[v.S][v.F]){
			stat[v.S][v.F] = 1;
			dfs(v.S, v.F);
		}
	}
}

int main(){
	fast_io;
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	for(int i = 0; i < m; i ++){
		char c1, c2; 
		int u1, u2;
		cin >> c1 >> u1 >> c2 >> u2;
//		cout << "in : " << c1 << " " << u1 << " | " << c2 << " " << u2 << endl;
		st(&a[i], c1, u1);
		st(&b[i], c2, u2);
	}
	for(int i = 0; i < n; i ++){
		stat[i][1] = -1;
	}
	for(int i = 0; i < m; i ++){
		adj[i][0][0][0].pb(a[i]);
		adj[i][0][0][0].pb(b[i]);
		
		adj[a[i].S][a[i].F][1][1].pb({0, i});
		adj[b[i].S][b[i].F][1][1].pb({0, i});
		
		out[a[i].S][a[i].F].pb({0, i});
		out[b[i].S][b[i].F].pb({0, i});
		
		pai[a[i].S][a[i].F].pb({b[i], i});
		pai[b[i].S][b[i].F].pb({a[i], i});
		
		stat[i][0] = (s[i] == '?') ? -1 : int(s[i] - '0');
	}
	
	for(int i = 0; i < m; i ++){
		if(stat[i][0] != -1 && !mark[i][0]){
			dfs(i, 0);
		}
	}
	for(int i = 0; i < m; i ++){
		if(stat[i][0] == -1){
			cout << "?";
		}
		else{
			cout << stat[i][0];
		}
	}
		
	return 0;
}

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