Submission #246282

#	Time	Username	Problem	Language	Result	Execution time	Memory
246282		vanic	Dijamant (COI16_dijament)	C++14	100 / 100	1089 ms	7600 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(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	string s, s1;
	vector < string > v;
	int p;
	bool sol;
	int iduc=1;
	for(int i=0; i<n; i++){
		cin >> s;
		cin >> s1;
		cin >> s1;
		v.clear();
		while(s1!=";"){
			v.push_back(s1);
			cin >> s1;
		}
		sol=1;
		if(ind.find(s)!=ind.end()){
			cout << "greska\n";
			continue;
		}
		for(int j=0; j<v.size(); j++){
			if(ind.find(v[j])==ind.end()){
				sol=0;
				break;
			}
		}
		if(!sol){
			cout << "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){
			cout << "greska\n";
			continue;
		}
		cout << "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:107:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:118:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:136:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<v.size(); j++){
                ~^~~~~~~~~
dijament.cpp:130:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(p==maxn){
   ^~

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