Submission #104661

#	Time	Username	Problem	Language	Result	Execution time	Memory
104661		Shtef	Ili (COI17_ili)	C++14	100 / 100	741 ms	62328 KiB

ili

#include <iostream>
#include <cstring>
#include <utility>

using namespace std;

typedef pair <char, int> pci;
#define x first
#define y second
#define mp make_pair

int n, m, mali[10005], veliki[10005];
string s;
pci koji[10005][2];

void dfs(int x){
	for(int i = 0 ; i < 2 ; ++i){
		pci o = koji[x][i];
		if(o.x == 'x'){
			mali[o.y] = 0;
		}
		else if(veliki[o.y]){
			veliki[o.y] = 0;
			dfs(o.y);
		}
	}
}

void postavinule(){
	for(int i = 1 ; i <= m ; ++i){
		if(veliki[i])
			continue;
		dfs(i);
	}
	for(int i = 1 ; i <= m ; ++i){
		if(veliki[i] != -1)
			continue;
		bool p = 1;
		for(int j = 0 ; j < 2 ; ++j){
			if(koji[i][j].x == 'x'){
				if(mali[koji[i][j].y]){
					p = 0;
					break;
				}
			}
			else{
				if(veliki[koji[i][j].y]){
					p = 0;
					break;
				}
			}
		}
		if(p){
			veliki[i] = 0;
		}
	}
}

bool imax[10005][10005], sadrz[10005];

void postavijedinice(){
	for(int i = 1 ; i <= m ; ++i){
		for(int j = 0 ; j < 2 ; ++j){
			if(koji[i][j].x == 'x'){
				if(mali[koji[i][j].y]){
					imax[i][koji[i][j].y] = 1;
				}
			}
			else{
				if(veliki[koji[i][j].y]){
					for(int v = 1 ; v <= n ; ++v){
						if(mali[v] && imax[koji[i][j].y][v]){
							imax[i][v] = 1;
						}
					}
				}
			}
		}
	}
	for(int i = 1 ; i <= m ; ++i){
		if(veliki[i] != -1)
			continue;
		for(int j = 1 ; j <= m ; ++j){
			sadrz[j] = 1;
			for(int v = 0 ; v < 2 ; ++v){
				if(koji[j][v].x == 'x'){
					if(mali[koji[j][v].y] && !imax[i][koji[j][v].y]){
						sadrz[j] = 0;
						break;
					}
				}
				else{
					if(veliki[koji[j][v].y] && !sadrz[koji[j][v].y]){
						sadrz[j] = 0;
						break;
					}
				}
			}
			if(sadrz[j] && veliki[j] == 1){
				veliki[i] = 1;
				break;
			}
		}
	}
}

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
cin >> s;
memset(mali, -1, sizeof(mali));
memset(veliki, -1, sizeof(veliki));
for(int i = 1 ; i <= m ; ++i){
	if(s[i - 1] == '?')
		continue;
	veliki[i] = s[i - 1] - '0';
}
for(int i = 1 ; i <= m ; ++i){
	for(int j = 0 ; j < 2 ; ++j){
		cin >> koji[i][j].x >> koji[i][j].y;
	}
}
postavinule();
/*
for(int i = 1 ; i <= n ; ++i){
	cout << mali[i] << ' ';
}
cout << endl;
for(int i = 1 ; i <= m ; ++i){
	cout << veliki[i] << ' ';
}
cout << endl;
*/
postavijedinice();
for(int i = 1 ; i <= m ; ++i){
	if(veliki[i] == -1){
		cout << "?";
	}
	else{
		char c = veliki[i] + '0';
		cout << c;
	}
}
cout << endl;

return 0;
}

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