Submission #96150

#	Time	Username	Problem	Language	Result	Execution time	Memory
96150		algorithm16	KOVANICE (COI15_kovanice)	C++14	0 / 100	1056 ms	41688 KiB

kovanice

#include<iostream>
#include<string>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
pair <vector <int>,vector <int> > v[300005];
int depth[300005],parent[300005],bio[300005],maxi=0,a[300005];
void dfs(int x,int par,int d) {
	parent[x]=par;
	depth[x]=max(depth[x],d);
	bio[x]=1;
	//cout <<x<<" "<<d<<endl;
	maxi=max(maxi,d);
	for(int i=0;i<(v[x].first).size();i++) {
		if(bio[(v[x].first)[i]]==1) continue;
		dfs((v[x].first)[i],x,d+1);
	}
	for(int i=0;i<(v[x].second).size();i++) {
		if(bio[(v[x].second)[i]]==1) continue;
		dfs((v[x].second)[i],parent[(v[x].second)[i]],d);
	}
}
void dfs2(int x,int par,int d) {
	depth[x]=-1;
	//cout <<x<<endl;
	for(int i=0;i<(v[x].first).size();i++) {
		if(bio[(v[x].first)[i]]==1) continue;
		dfs2((v[x].first)[i],x,d+1);
	}
	for(int i=0;i<(v[x].second).size();i++) {
		if(bio[(v[x].second)[i]]==1) continue;
		dfs2((v[x].second)[i],parent[(v[x].second)[i]],d);
	}
}
int main()
{
	int n,m,v1;
	cin >> n >> m >> v1;
	set <int> s1;
	for(int i=0;i<m;i++) {
		s1.insert(i);
		depth[i]=-1;
	}
	for(int i=0;i<v1;i++) {
		string s;
		cin >> s;
		int ind=0,b1=0,b2=0;
		for(int j=0;j<s.size();j++) {
			if(s[j]=='=' or s[j]=='<') ind=j;
		}
		int x=1;
		for(int j=ind-1;j>=0;j--) {
			b1+=(int(s[j])-48)*x;
			x*=10;
		}
		x=1;
		for(int j=s.size()-1;j>ind;j--) {
			b2+=(int(s[j])-48)*x;
			x*=10;
		}
		if(s[ind]=='=') {
			(v[b1-1].second).push_back(b2-1);
			(v[b2-1].second).push_back(b1-1);
		}
		if(s[ind]=='<') {
			(v[b1-1].first).push_back(b2-1);
			s1.erase(b2-1);
		}
	}
	for(set <int>::iterator it=s1.begin();it!=s1.end();it++) {
		//cout <<"s1 "<<(*it)<<endl;
		if(bio[(*it)]==1) continue;
		maxi=0;
		dfs((*it),(*it),1);
		//cout <<endl<<maxi<<endl;
		if(maxi==n) a[(*it)]=1;
		/*if(maxi!=n) {
			cout <<"a"<<endl;
			dfs2((*it),(*it),1);
		}
		for(int i=0;i<m;i++) {
			cout <<depth[i]<<" ";
		}
		cout <<endl;*/
	}
	for(int i=0;i<m;i++) {
		//cout <<a[i]<<endl;
		bio[i]=0;
		depth[i]=-1;
	}
	for(int i=0;i<m;i++) {
		if(a[i]==1 && bio[i]==0) dfs(i,i,1);
	}
	for(int i=0;i<m;i++) {
		if(depth[i]==-1) cout <<"?"<<endl;
		else cout <<"K"<<depth[i]<<endl;
	}
	return 0;
}
/*
5 8 6
1<2
2<3
4<5
5<6
6<7
7<8
*/

Compilation message (stderr)

kovanice.cpp: In function 'void dfs(int, int, int)':
kovanice.cpp:15:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<(v[x].first).size();i++) {
              ~^~~~~~~~~~~~~~~~~~~~
kovanice.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<(v[x].second).size();i++) {
              ~^~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'void dfs2(int, int, int)':
kovanice.cpp:27:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<(v[x].first).size();i++) {
              ~^~~~~~~~~~~~~~~~~~~~
kovanice.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<(v[x].second).size();i++) {
              ~^~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<s.size();j++) {
               ~^~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 10
• Subtask 4: 0 / 40