oj.uz

Submission #66356

# Submission time Handle Problem Language Result Execution time Memory
66356 2018-08-10T10:16:32 Z hamzqq9 Ili (COI17_ili) C++14
0 / 100
 2 ms 416 KB 
#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<505> bs[505],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];

}

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 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=n+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

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 416 KB Output isn't correct
4 Halted 0 ms 0 KB -