Submission #249137

#	Time	Username	Problem	Language	Result	Execution time	Memory
249137		vanic	KOVANICE (COI15_kovanice)	C++14	0 / 100	2075 ms	19064 KiB

kovanice

#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;

char scan(int &a){
	char c=getchar();
	a=0;
	while(c>='0' && c<='9'){
		a*=10;
		a+=c-'0';
		c=getchar();
	}
	return c;
}

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;
	scan(n);
	scan(m);
	scan(v);
	char c;
	int a, b;
	for(int i=0; i<v; i++){
		c=scan(a);
		scan(b);
		a--;
		b--;
		if(c=='<'){
			ms[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 (stderr)

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:70: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:80:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<ms[x].size(); i++){
               ~^~~~~~~~~~~~~

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