Submission #66366

#	Time	Username	Problem	Language	Result	Execution time	Memory
66366		hamzqq9	Ili (COI17_ili)	C++14	49 / 100	4018 ms	13196 KiB

ili

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<ii,int>
#define sz(x) (x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 1000000000
#define MOD 1000000007
#define N 10005
#define MAX 10000006
#define LOG 20
using namespace std;

int n,m;
int vis[N],val[N];
ii go[N];
char s[N],a[20];
bitset<N> bs[N],vbs;

int get_num(int bas,int son) {

	int res=0;

	for(int i=bas;i<=son;i++) {

		int dig=a[i]-'0';

		res=res*10+dig;

	}

	return res;

}

int parse() {

	int len=strlen(a+1);

	int add=(a[1]=='x'?0:n);

	return add+get_num(2,len);

}

void dfs(int node) {

	if(vis[node]) return ;

	vis[node]=1;

	val[node]=0;

	if(node<=n) return ;

	dfs(go[node].st);
	dfs(go[node].nd);

}

void fnd(int node) {

	if(vis[node]) return ;

	vis[node]=1;

	if(node<=n) return ;

	fnd(go[node].st);
	fnd(go[node].nd);

	bs[node]=bs[go[node].st]|bs[go[node].nd];

}

void f1(int node) {

	if(vis[node]) return ;

	vis[node]=1;

	if(node<=n) return ;

	f1(go[node].st);
	f1(go[node].nd);

	if(val[go[node].st]==1 || val[go[node].nd]==1) val[node]=1;

	if(val[go[node].st]==0 && val[go[node].nd]==0) val[node]=0;

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d %d",&n,&m);

	scanf("%s",s+1);

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

		scanf("%s",a+1);

		int node1=parse();

		scanf("%s",a+1);

		int node2=parse();

		go[n+i]={node1,node2};

	}

	for(int i=1;i<=n;i++) val[i]=2;

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

		if(s[i-n]=='?') val[i]=2;
		else val[i]=s[i-n]-'0';

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

		if(val[i]==0) {

			dfs(i);

		}

	}

	for(int it=1;it<=100;it++) {

	memset(vis,0,sizeof(vis));

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

		f1(i);

	}
	}

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

		vbs[i]=(val[i]>0);

	}

	memset(vis,0,sizeof(vis));

	for(int i=1;i<=n;i++) bs[i][i]=1;

	for(int i=n+1;i<=n+m;i++) fnd(i);

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

		if(val[i]!=2) continue ;

		for(int j=1;j<=n+m;j++) {

			if(val[j]==1 && (bs[i]|(bs[j]&vbs))==bs[i]) {

				val[i]=1;

				break ;

			}

		}

	}

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

		if(val[i]==2) printf("?");
		else printf("%c",'0'+val[i]);

	}

}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:107: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:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",s+1);
  ~~~~~^~~~~~~~~~
ili.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",a+1);
   ~~~~~^~~~~~~~~~
ili.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s",a+1);
   ~~~~~^~~~~~~~~~

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