oj.uz

답안 #66364

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
66364 2018-08-10T10:24:58 Z hamzqq9 Ili (COI17_ili) C++14
49 / 100
 18 ms 976 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];

}

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

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct

Subtask #2
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct
8 Correct 4 ms 624 KB Output is correct
9 Correct 4 ms 624 KB Output is correct
10 Correct 6 ms 624 KB Output is correct
11 Correct 4 ms 624 KB Output is correct
12 Correct 5 ms 624 KB Output is correct
13 Correct 3 ms 624 KB Output is correct
14 Correct 5 ms 624 KB Output is correct

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 624 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 624 KB Output is correct
6 Correct 3 ms 624 KB Output is correct
7 Correct 2 ms 624 KB Output is correct
8 Correct 4 ms 624 KB Output is correct
9 Correct 4 ms 624 KB Output is correct
10 Correct 6 ms 624 KB Output is correct
11 Correct 4 ms 624 KB Output is correct
12 Correct 5 ms 624 KB Output is correct
13 Correct 3 ms 624 KB Output is correct
14 Correct 5 ms 624 KB Output is correct
15 Runtime error 18 ms 976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Halted 0 ms 0 KB -