Submission #66402

#	Time	Username	Problem	Language	Result	Execution time	Memory
66402		MrTEK	Ili (COI17_ili)	C++14	0 / 100	5 ms	3112 KiB

ili

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define left ind+ind
#define right ind+ind+1
#define mid (l+r)/2
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'

typedef long long int ll;

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9;
const int N = 1e4 + 5;
const int M = 1e4 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef pair <int,int> pii;

int n,m,val[M],vis[M];

vector <int> ed[M],red[M],v[M],ned[M],rned[M];

void pre_dfs(int cur) {
	if (vis[cur]) return;
	vis[cur] = 1;
	for (auto i : red[cur]) {
		if (i > m) v[cur].pb(i);
		else {
			pre_dfs(i);
			for (auto j : v[i]) v[cur].pb(j);
		}
	}
}

void solve(int cur) {
	if (vis[cur]) return;
	vis[cur] = 1;
	if (cur > m) return;
	int ch1 = red[cur][0],ch2 = red[cur][1];
	if (val[cur] == 1 && val[ch1] == -1 && val[ch2] == 0) val[ch1] = 1;
	if (val[cur] == 1 && val[ch2] == -1 && val[ch1] == 0) val[ch2] = 1;
	if (val[cur] == 0) val[ch1] = val[ch2] = 0;
	solve(ch1);
	solve(ch2);
}

void dfs(int cur) {
	if (vis[cur]) return;
	vis[cur] = 1;
	for (auto i : ned[cur]) {
		dfs(i);
		if (val[i] == 0) val[cur] = 0;
	}
}

void dfs2(int cur) {
	if (vis[cur]) return;
	vis[cur] = 1;
	for (auto i : rned[cur]) {
		dfs2(i);
		if (val[i] == 1) val[cur] = 1;
	}
}

int main() {
	
	scanf("%d %d",&n,&m);

	memset(val,-1,sizeof val);

	for (int i = 1 ; i <= m ; i++) {
		char c;
		scanf(" %c",&c);
		if (c == '1') val[i] = 1;
		else if (c == '0') val[i] = 0;
		else val[i] = -1;
	}


	for (int i = 1 ; i <= m ; i++) {
		char c1,c2,c3,c4;
		scanf(" %c %c %c %c",&c1,&c2,&c3,&c4);
		int n1 = c2 - '0' + (c1 == 'x' ? m : 0), n2 = c4 - '0' + (c3 == 'x' ? m : 0);
		ed[n1].pb(i);
		ed[n2].pb(i);
		red[i].pb(n1);
		red[i].pb(n2);
	}

	for (int i = 1 ; i <= m ; i++) pre_dfs(i);

	for (int i = 1 ; i <= m ; i++) {
		sort(v[i].begin(),v[i].end());
		v[i].resize(unique(v[i].begin(),v[i].end()) - v[i].begin());
	}

	for (int i = 1 ; i <= m ; i++) {
		for (int j = i + 1 ; j <= m ; j++) {
			int x = i , y = j;
			if (len(v[x]) > len(v[y])) swap(x,y);
			bool flag = true;
			for (auto k : v[x]) {
				int tut = lower_bound(v[y].begin(),v[y].end(),k) - v[y].begin();
				if (y < len(v[y]) || v[y][tut] != k) {flag = false;break;} 
			}
			if (flag) ned[x].pb(y);
			if (flag) rned[y].pb(x);
		}
	}

	for (int asd = 0; asd < 2; asd++) {
		memset(vis,0,sizeof vis);
		for (int i = 1 ; i <= m; i++) solve(i);
	}

	for (int i = 1 ; i <= m ; i++) {
		int flag = 0;
		for (auto j : v[i]) {
			if (val[j] == -1) flag = -1;
			if (val[j] == 1) {flag = 1; break;}
		}
		if (val[i] == -1) val[i] = flag;
	}

	// for (int i = 1 ; i <= m ; i++) {
	// 	if (val[i] == 1) printf("1");
	// 	else if(val[i] == 0) printf("0");
	// 	else printf("?");
	// }

	// puts("");


	memset(vis,0,sizeof vis);

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

	memset(vis,0,sizeof vis);

	for (int i = 1 ; i <= m ; i++) dfs2(i);

	for (int i = 1 ; i <= m ; i++) {
		if (val[i] == 1) printf("1");
		else if(val[i] == 0) printf("0");
		else printf("?");
	}
}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
ili.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
   ~~~~~^~~~~~~~~~
ili.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %c %c %c",&c1,&c2,&c3,&c4);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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