Submission #350141

#	Time	Username	Problem	Language	Result	Execution time	Memory
350141		arnold518	Ili (COI17_ili)	C++14	100 / 100	400 ms	748 KiB

ili

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e4;

int N, M;
char S[MAXN+10];
pii A[MAXN+10];

int B[MAXN+10], C[MAXN+10];

char ans[MAXN+10];

void dfs(int now)
{
	if(now<=N)
	{
		B[now]=0;
		return;
	}
	dfs(A[now].first);
	dfs(A[now].second);
}

void dfs2(int now)
{
	if(now<=N)
	{
		C[now]=0;
		return;
	}
	dfs2(A[now].first);
	dfs2(A[now].second);
}

int main()
{
	scanf("%d%d", &N, &M);
	scanf(" %s", S+N+1);
	for(int i=N+1; i<=N+M; i++)
	{
		char c1, c2;
		int d1, d2;
		scanf(" %c%d %c%d", &c1, &d1, &c2, &d2);
		if(c1=='c') d1+=N;
		if(c2=='c') d2+=N;
		A[i]={d1, d2};
	}

	for(int i=N+1; i<=N+M; i++) ans[i]='?';

	for(int i=1; i<=N; i++) B[i]=1;
	for(int i=N+1; i<=N+M; i++) if(S[i]=='0') dfs(i);
	for(int i=N+1; i<=N+M; i++)
	{
		B[i]=B[A[i].first]|B[A[i].second];
		if(B[i]==0) ans[i]='0';
	}

	for(int i=N+1; i<=N+M; i++)
	{
		if(B[i]==1)
		{
			for(int j=1; j<=N; j++) C[j]=B[j];
			dfs2(i);
			bool flag=true;
			for(int j=N+1; j<=N+M; j++)
			{
				C[j]=C[A[j].first]|C[A[j].second];
				if(S[j]=='1' && C[j]==0) flag=false;
			}
			if(!flag) ans[i]='1';
		}
	}
	printf("%s\n", ans+N+1);
}

Compilation message (stderr)

ili.cpp: In function 'int main()':
ili.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   42 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
ili.cpp:43:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |  scanf(" %s", S+N+1);
      |  ~~~~~^~~~~~~~~~~~~~
ili.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |   scanf(" %c%d %c%d", &c1, &d1, &c2, &d2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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