Submission #66347

#	Time	Username	Problem	Language	Result	Execution time	Memory
66347		osmanorhan	Ili (COI17_ili)	C++17	100 / 100	598 ms	5880 KiB

ili

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <climits>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <cassert>
#include <vector>
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
#define umax( x , y ) x = max( x , (y) )
#define umin( x , y ) x = min( x , (y) )
#define For( i , a ) for(int i=1;i<=a;i++)
#define ort (b+s)/2
#define y2 asrwjaelkf
#define y1 asseopirwjaelkf
#define set multiset

using namespace std;

typedef long long Lint;
typedef double db;
typedef pair<int,int> ii;
typedef pair<int,char> ic;
typedef pair<db,db> dd;
typedef pair<ii,int> iii;
typedef pair<ii,ii> i4;

const int maxn = 100020;
const int maxm = 1000020;
const int MOd = 998244353;

int a, b, q;
int x[maxn], c[maxn];
int ar[maxn], bs[maxn];
ii con[maxn];
vector<int> w[maxn];

int Or( int x, int y ) {
	if( x > y ) swap( x, y );
	if( y == 0 ) return 0;
	if( y == 1 ) return 1;
	if( x == 0 || x == 2 ) return 2;
	return 1;
}

int get( string s ) {
	int x = 0;
	for(int i=1;i<s.size();i++)
		x *= 10, x += s[i]-'0';
	if( s[0] == 'c' ) x += a;
	return x;
}

bool can( int t ) {
	for(int i=1;i<=a+b;i++) bs[i] = ar[i];
	bs[t] = 0;
	for(int i=t;i>a;i--)
		if( bs[i] == 0 ) {
			if( bs[ con[i].fi ] == 1 || bs[ con[i].se ] == 1 ) return false;
			bs[ con[i].fi ] = bs[ con[i].se ] = 0;
		}
	for(int i=a+1;i<=a+b;i++) {
		int h = Or( bs[ con[i].fi ], bs[ con[i].se ] );
		if( h != 2 ) {
			if( bs[i] != 2 && bs[i] != h ) return false;
			bs[i] = h;
		}
	}
	return true;
}

int main() {

    //freopen("asd.in","r",stdin);
    //freopen("output17.txt","w",stdout);

	scanf("%d %d",&a,&b);
	for(int i=1;i<=a;i++) ar[i] = 2;
	for(int i=1;i<=b;i++) {
		char ch;
		scanf(" %c",&ch);
		if( ch == '0' ) ar[a+i] = 0;
		else if( ch == '1' ) ar[a+i] = 1;
		else ar[a+i] = 2;
	}

	for(int i=1;i<=b;i++) {
		string s1, s2;
		cin >> s1 >> s2;
	
		int t1 = get( s1 );
		int t2 = get( s2 );
		con[a+i] = ii( t1, t2 );
		w[t1].pb( a+i );
		w[t2].pb( a+i );
	}
	for(int i=a+b;i>a;i--)
		if( ar[i] == 0 ) ar[ con[i].fi ] = 0, ar[ con[i].se ] = 0;

	for(int i=a+1;i<=b+a;i++) {
		int t = i;
		if( ar[t] != 2 ) continue;
		//printf("-- %d %d\n",con[t].fi,con[t].se);
		int h1 = Or( ar[ con[t].fi ], ar[ con[t].se ] );
		if( h1 != 2 ) {
			ar[t] = h1;
		} else {
			//printf("asd %d\n",i);
			if( !can( t ) ) ar[t] = 1;
		}
	}
	for(int i=a+1;i<=b+a;i++) {
		if( ar[i] == 2 ) printf("?");
		else printf("%d",ar[i]);
	}
	printf("\n");
	return 0;
}

Compilation message (stderr)

ili.cpp: In function 'int get(std::__cxx11::string)':
ili.cpp:57:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<s.size();i++)
              ~^~~~~~~~~
ili.cpp: In function 'int main()':
ili.cpp:86:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&a,&b);
  ~~~~~^~~~~~~~~~~~~~~
ili.cpp:90:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&ch);
   ~~~~~^~~~~~~~~~~

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