oj.uz

답안 #246271

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
246271 2020-07-08T13:51:35 Z vanic Dijamant (COI16_dijament) C++14
13 / 100
 83 ms 4092 KB 
#include <cstdio>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <string.h>

using namespace std;

const int maxn=1005;

map < string, int > ind;
vector < int > ms[maxn];
bool spec[maxn];
vector < int > svi;
int dp[maxn];

void scan(int &a){
	a=0;
	char c=getchar();
	while(c>='0' && c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar();
	}
}

void scan1(string &s, vector < string > &v){
	s.clear();
	v.clear();
	char c=getchar();
	while(c!=' '){
		s.push_back(c);
		c=getchar();
	}
	getchar();
	getchar();
	c=getchar();
	string s1;
	while(c!=';'){
		while(c!=' '){
			s1.push_back(c);
			c=getchar();
		}
		v.push_back(s1);
		s1.clear();
		c=getchar();
	}
	getchar();
}

int dfs(int x){
	if(dp[x]){
		return dp[x];
	}
	int y;
	for(int i=0; i<ms[x].size(); i++){
		y=dfs(ms[x][i]);
		if(y==maxn){
			return maxn;
		}
		if(y!=-1){
			if(dp[x] && dp[x]!=dp[y]){
				return maxn;
			}
			dp[x]=y;
		}
	}
	if(!dp[x]){
		if(spec[x]){
			dp[x]=x;
		}
		else{
			dp[x]=-1;
		}
	}
	return dp[x];
}

int main(){
	int n;
	scan(n);
	string s;
	vector < string > v;
	int p;
	bool sol;
	for(int i=0; i<n; i++){
		scan1(s, v);
		sol=1;
		if(ind[s]){
			printf("greska\n");
			continue;
		}
		for(int j=0; j<v.size(); j++){
			if(!ind[v[j]]){
				sol=0;
				break;
			}
		}
		if(!sol){
			printf("greska\n");
			continue;
		}
		memset(spec, 0, sizeof(spec));
		for(int j=0; j<v.size(); j++){
			spec[ind[v[j]]]=1;
		}
		memset(dp, 0, sizeof(dp));
//		cout << "Na " << s << ": ";
		for(int j=0; j<svi.size(); j++){
			if(!dp[svi[j]]){
				p=dfs(svi[j]);
//				printf("%d ", dp[svi[j]]);
				if(p==maxn){
					break;
				}
			}
		}
//		printf("\n");
		if(p==maxn){
			printf("greska\n");
			continue;
		}
		printf("ok\n");
		ind[s]=i+1;
		svi.push_back(i+1);
		for(int j=0; j<v.size(); j++){
			ms[ind[v[j]]].push_back(ind[s]);
		}
	}

	return 0;
}

Compilation message

dijament.cpp: In function 'int dfs(int)':
dijament.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
dijament.cpp: In function 'int main()':
dijament.cpp:96:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:107:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:112:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<svi.size(); j++){
                ~^~~~~~~~~~~
dijament.cpp:129:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:122:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(p==maxn){
   ^~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 6 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Incorrect 6 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 83 ms 4092 KB Output isn't correct
2 Halted 0 ms 0 KB -