oj.uz

Submission #249141

# Submission time Handle Problem Language Result Execution time Memory
249141 2020-07-14T12:21:46 Z vanic KOVANICE (COI15_kovanice) C++14
50 / 100
 2000 ms 16120 KB 
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <array>
#include <bitset>

using namespace std;

const int maxn=3e5+5;

vector < int > ms[maxn];
int val[maxn];
int sol[maxn];

struct union_find{
	int parent[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
		}
	}
	int find(int x){
		if(parent[x]==x){
			return x;
		}
		return parent[x]=find(parent[x]);
	}
	void update(int x, int y){
		x=find(x);
		y=find(y);
		if(ms[x].size()>ms[y].size()){
			swap(x, y);
		}
		parent[x]=y;
		for(int i=0; i<ms[x].size(); i++){
			ms[y].push_back(ms[x][i]);
		}
		ms[x].clear();
	}
	bool query(int x, int y){
		return find(x)==find(y);
	}
};

union_find U;

int dfs(int x){
	x=U.find(x);
	if(val[x]){
		return val[x];
	}
	for(int i=0; i<ms[x].size(); i++){
		val[x]=max(val[x], dfs(ms[x][i]));
	}
	val[x]++;
	return val[x];
}

void rijesi(int x){
	x=U.find(x);
	sol[x]=val[x];
	for(int i=0; i<ms[x].size(); i++){
		if(val[U.find(ms[x][i])]==val[x]-1){
			rijesi(ms[x][i]);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, v;
	cin >> n >> m >> v;
	char c;
	int a, b;
	string s;
	int pos;
	for(int i=0; i<v; i++){
		cin >> s;
		a=0;
		b=0;
		pos=0;
		while(s[pos]>='0' && s[pos]<='9'){
			a*=10;
			a+=s[pos]-'0';
			pos++;
		}
		c=s[pos];
		pos++;
		while(pos<s.size()){
			b*=10;
			b+=s[pos]-'0';
			pos++;
		}
		a--;
		b--;
		if(c=='<'){
			ms[U.find(b)].push_back(a);
		}
		else{
			if(!U.query(a, b)){
				U.update(a, b);
			}
		}
	}
	for(int i=0; i<m; i++){
		if(!val[U.find(i)]){
			dfs(U.find(i));
		}
	}
	for(int i=0; i<m; i++){
		if(val[i]==n){
			rijesi(i);
		}
	}
	for(int i=0; i<m; i++){
		if(sol[U.find(i)]){
			cout << "K" << sol[U.find(i)] << '\n';
		}
		else{
			cout << "?" << '\n';
		}
	}
	return 0;
}

Compilation message

kovanice.cpp: In member function 'void union_find::update(int, int)':
kovanice.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<ms[x].size(); i++){
                ~^~~~~~~~~~~~~
kovanice.cpp: In function 'int dfs(int)':
kovanice.cpp:59:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
kovanice.cpp: In function 'void rijesi(int)':
kovanice.cpp:69:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:98:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pos<s.size()){
         ~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8576 KB Output is correct
2 Correct 6 ms 8576 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 12024 KB Output is correct
2 Correct 82 ms 13304 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2094 ms 9216 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 2035 ms 16120 KB Time limit exceeded
2 Halted 0 ms 0 KB -