Submission #246279

#	Time	Username	Problem	Language	Result	Execution time	Memory
246279		vanic	Dijamant (COI16_dijament)	C++14	13 / 100	72 ms	384 KiB

dijament

#include <cstdio>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <bitset>
#include <assert.h>
#include <string.h>

using namespace std;

const int maxn=1005;

map < string, int > ind;
vector < int > ms[maxn];
bool spec[maxn];
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;
	int iduc=1;
	for(int i=0; i<n; i++){
		scan1(s, v);
		sol=1;
		if(ind.find(s)!=ind.end()){
			printf("greska\n");
			continue;
		}
		for(int j=0; j<v.size(); j++){
			if(ind.find(v[j])==ind.end()){
				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));
		for(int j=1; j<iduc; j++){
			if(!dp[j]){
				p=dfs(j);
				if(p==maxn){
					break;
				}
			}
		}
		if(p==maxn){
			assert(0);
			printf("greska\n");
			continue;
		}
		printf("ok\n");
		ind[s]=iduc;
		for(int j=0; j<v.size(); j++){
			ms[ind[v[j]]].push_back(iduc);
		}
		iduc++;
	}

	return 0;
}

Compilation message (stderr)

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:97:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:108:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:127:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 29
• Subtask 4: 0 / 44