oj.uz

Submission #206515

# Submission time Handle Problem Language Result Execution time Memory
206515 2020-03-03T16:33:23 Z algorithm16 KOVANICE (COI15_kovanice) C++14
50 / 100
 2000 ms 25016 KB 
#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++) {
		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

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:19: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:39:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=ind+1;j<s.size();j++) {
                   ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14456 KB Output is correct
2 Correct 14 ms 14456 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 20728 KB Output is correct
2 Correct 87 ms 20600 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 15096 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2076 ms 25016 KB Time limit exceeded
2 Halted 0 ms 0 KB -