oj.uz

Submission #245718

# Submission time Handle Problem Language Result Execution time Memory
245718 2020-07-07T09:01:36 Z vanic Ili (COI17_ili) C++14
7 / 100
 7 ms 1920 KB 
#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;

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 probaj(int x);


void gore(int x){
	val[x]=1;
	probaj(x);
	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]);
		}
	}
	else if(ms[x].size()==2){
		if(!val[ms[x][0]] && val[ms[x][1]]==-1){
			gore(ms[x][1]);
		}
		else if(!val[ms[x][1]] && val[ms[x][0]]==-1){
			gore(ms[x][0]);
		}
	}
}

bitset < maxn > bio;
bitset < maxn > sad;

void dfs(int x){
	bio[x]=1;
	sad[x]=1;
	for(int i=0; i<up[x].size(); i++){
		if(val[up[x][i]]!=1){
			if(bio[up[x][i]]){
				if(!sad[up[x][i]]){
					gore(up[x][i]);
				}
			}
			else{
				dfs(up[x][i]);
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	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 && val[ms[i+n][0]]==-1 && val[ms[i+n][1]]==-1){
			dfs(ms[i+n][0]);
			sad.reset();
			if(bio[ms[i+n][1]]){
				gore(ms[i+n][1]);
			}
			else{
				dfs(ms[i+n][1]);
				sad.reset();
			}
			bio.reset();
		}
	}
	for(int i=0; i<m; i++){
		if(val[i+n]==-1){
			cout << '?';
		}
		else{
			cout << val[i+n];
		}
	}
	cout << '\n';
	return 0;
}

Compilation message

ili.cpp: In function 'int pretvori(std::__cxx11::string)':
ili.cpp:25: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:37: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:46:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
ili.cpp:51: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 dfs(int)':
ili.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<up[x].size(); i++){
               ~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1792 KB Output is correct
2 Correct 5 ms 1792 KB Output is correct
3 Correct 6 ms 1792 KB Output is correct
4 Correct 6 ms 1920 KB Output is correct
5 Correct 6 ms 1896 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 7 ms 1792 KB Output is correct
8 Correct 7 ms 1896 KB Output is correct
9 Incorrect 6 ms 1896 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1792 KB Output is correct
2 Correct 5 ms 1792 KB Output is correct
3 Correct 6 ms 1792 KB Output is correct
4 Correct 6 ms 1920 KB Output is correct
5 Correct 6 ms 1896 KB Output is correct
6 Correct 7 ms 1792 KB Output is correct
7 Correct 7 ms 1792 KB Output is correct
8 Correct 7 ms 1896 KB Output is correct
9 Incorrect 6 ms 1896 KB Output isn't correct
10 Halted 0 ms 0 KB -