oj.uz

Submission #104661

# Submission time Handle Problem Language Result Execution time Memory
104661 2019-04-08T15:10:52 Z Shtef Ili (COI17_ili) C++14
100 / 100
 741 ms 62328 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 5 ms 2176 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 5 ms 1664 KB Output is correct
11 Correct 5 ms 1920 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 4 ms 1792 KB Output is correct
14 Correct 5 ms 2304 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 5 ms 2176 KB Output is correct
9 Correct 4 ms 1664 KB Output is correct
10 Correct 5 ms 1664 KB Output is correct
11 Correct 5 ms 1920 KB Output is correct
12 Correct 4 ms 1664 KB Output is correct
13 Correct 4 ms 1792 KB Output is correct
14 Correct 5 ms 2304 KB Output is correct
15 Correct 47 ms 21340 KB Output is correct
16 Correct 311 ms 26248 KB Output is correct
17 Correct 164 ms 22568 KB Output is correct
18 Correct 411 ms 46300 KB Output is correct
19 Correct 244 ms 25208 KB Output is correct
20 Correct 741 ms 43228 KB Output is correct
21 Correct 653 ms 62328 KB Output is correct
22 Correct 182 ms 57052 KB Output is correct
23 Correct 170 ms 60792 KB Output is correct
24 Correct 210 ms 61048 KB Output is correct
25 Correct 176 ms 40312 KB Output is correct
26 Correct 180 ms 39472 KB Output is correct
27 Correct 179 ms 39956 KB Output is correct
28 Correct 162 ms 38392 KB Output is correct
29 Correct 191 ms 38900 KB Output is correct
30 Correct 202 ms 39288 KB Output is correct
31 Correct 324 ms 49656 KB Output is correct
32 Correct 351 ms 56696 KB Output is correct