Submission #245772

#	Time	Username	Problem	Language	Result	Execution time	Memory
245772		vanic	Ili (COI17_ili)	C++14	100 / 100	562 ms	2688 KiB

ili

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <string.h>
#include <bitset>

using namespace std;


const int maxn=2e4+5;

int n, m;
vector < int > ms[maxn];
vector < int > up[maxn];
vector < int > boje[maxn];
int kol[maxn];
int val[maxn];

int pretvori(string x){
	int br=0;
	for(int i=1; i<x.size(); i++){
		br*=10;
		br+=x[i]-'0';
	}
	return br;
}


void gore(int x){
	val[x]=1;
	for(int i=0; i<up[x].size(); i++){
		if(val[up[x][i]]==-1){
			gore(up[x][i]);
		}
	}
}

void dolje(int x){
	val[x]=0;
	for(int i=0; i<ms[x].size(); i++){
		if(val[ms[x][i]]==-1){
			dolje(ms[x][i]);
		}
	}
	for(int i=0; i<up[x].size(); i++){
		if(ms[up[x][i]].size()==1 && val[up[x][i]]==-1){
			dolje(up[x][i]);
		}
		else if(val[up[x][i]]==-1 && !val[ms[up[x][i]][0]] && !val[ms[up[x][i]][1]]){
			dolje(up[x][i]);
		}
	}
}

void probaj(int x){
	val[x]=1;
	if(ms[x].size()==1){
		if(val[ms[x][0]]==-1){
			gore(ms[x][0]);
			probaj(ms[x][0]);
		}
	}
	else if(ms[x].size()==2){
		if(!val[ms[x][0]] && val[ms[x][1]]==-1){
			gore(ms[x][1]);
			probaj(ms[x][1]);
		}
		else if(!val[ms[x][1]] && val[ms[x][0]]==-1){
			gore(ms[x][0]);
			probaj(ms[x][0]);
		}
	}
}

bitset < maxn > bio;

bool dfs(int x){
	if(val[x]==1){
		return 1;
	}
	bio[x]=1;
	for(int i=0; i<ms[x].size(); i++){
		if(val[ms[x][i]]==-1 && !bio[ms[x][i]]){
			if(dfs(ms[x][i])){
				return 1;
			}
		}
	}
	bool p;
	for(int i=0; i<up[x].size(); i++){
		if(bio[up[x][i]]){
			continue;
		}
		p=1;
		for(int j=0; j<ms[up[x][i]].size(); j++){
			if(!bio[ms[up[x][i]][j]] && val[ms[up[x][i]][j]]!=0){
				p=0;
			}
		}
		if(p){
			if(dfs(up[x][i])){
				return 1;
			}
		}
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	string s;
	cin >> s;
	string a, b;
	int br1, br2;
	memset(val, -1, sizeof(val));
	for(int i=0; i<m; i++){
		cin >> a >> b;
		br1=pretvori(a);
		br2=pretvori(b);
		br1--;
		br2--;
		if(a[0]=='c'){
			br1+=n;
		}
		if(b[0]=='c'){
			br2+=n;
		}
		if(br1!=br2){
			up[br1].push_back(i+n);
			up[br2].push_back(i+n);
			ms[i+n].push_back(br1);
			ms[i+n].push_back(br2);
		}
		else{
			up[br1].push_back(i+n);
			ms[i+n].push_back(br1);
		}
	}
	for(int i=0; i<m; i++){
		if(val[i+n]==-1){
			if(s[i]=='0'){
				dolje(i+n);
			}
			else if(s[i]=='1'){
				gore(i+n);
			}
		}
	}
	for(int i=0; i<m; i++){
		if(val[i+n]==1){
			probaj(i+n);
		}
	}
	for(int i=0; i<m; i++){
		if(val[i+n]==-1){
			if(dfs(i+n)){
				gore(i+n);
				probaj(i+n);
			}
			bio.reset();
		}
	}
//	cout << val[111] << " " << val[17] << " " << val[19] << endl;
	for(int i=0; i<m; i++){
/*		if(i==184){
			cout << endl;
			cout << val[i+n] << endl;
		}*/
		if(val[i+n]==-1){
			cout << '?';
		}
		else{
			cout << val[i+n];
		}
	}
	return 0;
}

Compilation message (stderr)

ili.cpp: In function 'int pretvori(std::__cxx11::string)':
ili.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<x.size(); i++){
               ~^~~~~~~~~
ili.cpp: In function 'void gore(int)':
ili.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<up[x].size(); i++){
               ~^~~~~~~~~~~~~
ili.cpp: In function 'void dolje(int)':
ili.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
ili.cpp:50:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<up[x].size(); i++){
               ~^~~~~~~~~~~~~
ili.cpp: In function 'bool dfs(int)':
ili.cpp:87:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
ili.cpp:95:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<up[x].size(); i++){
               ~^~~~~~~~~~~~~
ili.cpp:100:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<ms[up[x][i]].size(); j++){
                ~^~~~~~~~~~~~~~~~~~~~

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