Submission #206516

#	Time	Username	Problem	Language	Result	Execution time	Memory
206516		algorithm16	KOVANICE (COI15_kovanice)	C++14	0 / 100	2091 ms	24952 KiB

kovanice

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int n,m,v1,d[300005],cnt[300005],bio[300005];
vector <int> v[300005],eq[300005];
int dfs(int x,int d1) {
	int ret=d1;
	for(int i=0;i<v[x].size();i++) {
		if(d[v[x][i]]>=d1+1) continue;
		ret=max(ret,dfs(v[x][i],d1+1));
	}
	if(ret==n) d[x]=d1;
	return ret;
}
void dfs2(int x,int a) {
	d[x]=a;
	bio[x]=1;
	for(int i=0;i<eq[x].size();i++) {
		if(bio[eq[x][i]]) continue;
		dfs2(eq[x][i],a);
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> v1;
	for(int i=0;i<v1;i++) {
		string s;
		cin >> s;
		int ind=0,a=0,b=0;
		while(s[ind]>='0' && s[ind]<='9') {
			a*=10;
			a+=s[ind]-'0';
			ind+=1;
		}
		for(int j=ind+1;j<s.size();j++) {
			b*=10;
			b+=s[j]-'0';
		}
		if(s[ind]=='=') {
			eq[a-1].push_back(b-1);
			eq[b-1].push_back(a-1);
		}
		else if(s[ind]=='<') {
			v[a-1].push_back(b-1);
			cnt[b-1]+=1;
		}
		else {
			v[b-1].push_back(a-1);
			cnt[a-1]+=1;
		}
	}
	for(int i=0;i<m;i++) {
		if(cnt[i]==0) dfs(i,1);
	}
	for(int i=0;i<m;i++) {
		if(d[i] && bio[i]==0) dfs2(i,d[i]);
	}
	for(int i=0;i<m;i++) {
		if(d[i]) cout << "K" << d[i] << "\n";
		else cout << "?\n";
	}
	return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'int dfs(int, int)':
kovanice.cpp:10:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
kovanice.cpp: In function 'void dfs2(int, int)':
kovanice.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<eq[x].size();i++) {
              ~^~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=ind+1;j<s.size();j++) {
                   ~^~~~~~~~~

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