oj.uz

Submission #102354

# Submission time Handle Problem Language Result Execution time Memory
102354 2019-03-24T13:21:01 Z JedrzejOlkowski Dijamant (COI16_dijament) C++14
100 / 100
 464 ms 9916 KB 
#include<bits/stdc++.h>
using namespace std;

const int N=2000+10;
const int BS=50;
const int M=31;

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

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 CzyPrzodek(int v, int u){
	if( ( Przodek[v][ u/M ]&(1<<(u%M)) )>0 ) return 1;
	if( ( Przodek[u][ v/M ]&(1<<(v%M)) )>0 ) return 1;
	return 0;
}

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( CzyPrzodek(i, id) || i==id ) continue;
		for(int j=0; j<BS; j++){
			if( (Przodek[id][j]&Przodek[i][j])>0 ){
				DodajKuzyna(i);
				break;
			}
		}
	}
}

int main (){
	int n, wejscie, d; string slowo;
	cin>>n;
	getline(cin, slowo);
	for(int i=1; i<=n; i++){
		wejscie=ZamienWejscie();
		if( wejscie==0 ){
			cout<<"greska\n";
			continue;
		}
		d=CzyDiament(n);
		if( d==0 ){
			IdWie[rep]=0; id--;
			cout<<"greska\n";
			continue;
		}
		LiczPrzodkowKuzynow(n);
		cout << "ok\n";
	}
	return 0;
}

Subtask #1
13.0 / 13.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 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #2
14.0 / 14.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 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #3
29.0 / 29.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 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 7 ms 768 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 3 ms 612 KB Output is correct
15 Correct 4 ms 512 KB Output is correct
16 Correct 2 ms 512 KB Output is correct
17 Correct 4 ms 640 KB Output is correct
18 Correct 3 ms 640 KB Output is correct
19 Correct 4 ms 512 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 4 ms 512 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 422 ms 9916 KB Output is correct
2 Correct 464 ms 9568 KB Output is correct
3 Correct 199 ms 3576 KB Output is correct
4 Correct 13 ms 1280 KB Output is correct
5 Correct 34 ms 2808 KB Output is correct
6 Correct 46 ms 1912 KB Output is correct
7 Correct 46 ms 2040 KB Output is correct
8 Correct 59 ms 2296 KB Output is correct
9 Correct 75 ms 2252 KB Output is correct
10 Correct 32 ms 1784 KB Output is correct
11 Correct 34 ms 1784 KB Output is correct
12 Correct 404 ms 9456 KB Output is correct