oj.uz

Submission #102345

# Submission time Handle Problem Language Result Execution time Memory
102345 2019-03-24T12:29:21 Z JedrzejOlkowski Dijamant (COI16_dijament) C++14
13 / 100
 302 ms 4656 KB 
#include<bits/stdc++.h>
using namespace std;

const int N=1e3+10;
const int BS=40;
const int M=31;

int Przodek[N][BS];
int Kuzyn[N][BS];
int MaskaSasiedzi[BS];
int Kra[N][N];

unordered_map<string, int>IdWie;
int id=0;
vector<int>Sasiedzi;
string rep;

int Literka(char znak){
	if( (int)znak>=97 && (int)znak<=122 ) return 1;
	return 0;
}


int ZamienWejscie(){
	string slowo, aktu; int j, i;
	getline(cin, slowo); Sasiedzi.clear();
	for(i=0; i<(int)slowo.size(); i++){
		j=i; rep=slowo[i];
		while( Literka(slowo[j+1]) ){
			j++;
			rep+=slowo[j];
		}
		if( IdWie[rep]>0 ) return 0;
		break;
	}
	for(i=j+4; i<(int)slowo.size(); i++){
		if( slowo[i]==';' ) break;
		aktu=slowo[i]; j=i;
		while( Literka(slowo[j+1]) ){
			j++;
			aktu+=slowo[j];
		}
		if( IdWie[aktu]==0 ) return 0;
		Sasiedzi.push_back( IdWie[aktu] );
		i=j+1;
	}
	IdWie[rep]=++id;
	return 1;
}

int CzyDiament(int n){
	for(int i=0; i<BS; i++) MaskaSasiedzi[i]=0;
	for(int i=0; i<(int)Sasiedzi.size(); i++)	MaskaSasiedzi[ Sasiedzi[i]/M ]+= (1<<(Sasiedzi[i]%M));
	for(int i=0; i<(int)Sasiedzi.size(); i++){
		for(int j=0; j<BS; j++){
			if( (Kuzyn[ Sasiedzi[i] ][j]&MaskaSasiedzi[j])>0 ) return 0;
		}	
	}
	return 1;
}

void DodajKuzyna(int aktu){
	Kuzyn[id][ aktu/M ]+=(1<<(aktu%M));
	Kuzyn[aktu][ id/M ]+=(1<<(id%M));
}

int NiePrzodek(int v, int u){
	if( ( Przodek[v][ u/M ]&(1<<(u%M)) )>0 ) return 0;
	if( ( Przodek[u][ v/M ]&(1<<(v%M)) )>0 ) return 0;
	return 1;
}

void LiczPrzodkowKuzynow(int n){
	for(int i=0; i<(int)Sasiedzi.size(); i++){
		for(int j=0; j<BS; j++) Przodek[id][j]=( Przodek[ Sasiedzi[i] ][j] | Przodek[id][j] );
		Kra[ Sasiedzi[i] ][id]=1;
	}
	Przodek[ id ][ id/M ]+=(1<<(id%M));
	for(int i=1; i<=n; i++){
		if( NiePrzodek(i, id )==0 || i==id ) continue;
		for(int j=0; j<BS; j++){
			if( (Przodek[id][j]&Przodek[i][j])>0 ) DodajKuzyna(i);
		}
	}
}

int main (){
	int n, wejscie, d; string slowo;
	cin>>n;
	getline(cin, slowo);
	for(int i=1; i<=n; i++){
		wejscie=ZamienWejscie();
	//	cout << endl;
	//	cout << "I " << i << ": " << rep << endl;
		if( wejscie==0 ){
			cout<<"greska\n";
			continue;
		}
		d=CzyDiament(n);
		if( d==0 ){
			IdWie[rep]=0; id--;
			cout<<"greska\n";
			continue;
		}
	//	cout << "rep " << rep << ": " << id << endl;
		LiczPrzodkowKuzynow(n);
	//	cout << "kuzyni i przodkowe po " << endl;
	//	for(int j=1; j<=n; j++) cout<<"("<<j<<", "<<Przodek[j][0]<<"), ";
	//	cout << endl;
	//	for(int j=1; j<=n; j++) cout<<"("<<j<<", "<<Kuzyn[j][0]<<"), ";
	//	cout << endl;
			
		cout << "ok\n";
		//cout << i << "-" << wejscie << ": ";
		//for(int j=0; j<(int)Sasiedzi.size(); j++) cout << Sasiedzi[j] << " ";
		//cout << endl;
	}
	return 0;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 4328 KB Output is correct
2 Correct 302 ms 4656 KB Output is correct
3 Correct 134 ms 512 KB Output is correct
4 Incorrect 8 ms 896 KB Output isn't correct
5 Halted 0 ms 0 KB -