Submission #249152

#	Time	Username	Problem	Language	Result	Execution time	Memory
249152		vanic	KOVANICE (COI15_kovanice)	C++14	100 / 100	333 ms	39160 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{
	vector < int > komp[maxn];
	int parent[maxn];
	union_find(){
		for(int i=0; i<maxn; i++){
			parent[i]=i;
			komp[i].push_back(i);
		}
	}
	void update(int x, int y){
		x=parent[x];
		y=parent[y];
		if(komp[x].size()>komp[y].size()){
			swap(x, y);
		}
		for(int i=0; i<komp[x].size(); i++){
			komp[y].push_back(komp[x][i]);
			parent[komp[x][i]]=y;
		}
		komp[x].clear();
	}
	bool query(int x, int y){
		return parent[x]==parent[y];
	}
};

union_find U;

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

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

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[b].push_back(a);
		}
		else{
			if(!U.query(a, b)){
				U.update(a, b);
			}
		}
	}
	for(int i=0; i<m; i++){
		if(!val[U.parent[i]]){
			dfs(U.parent[i]);
		}
	}
	for(int i=0; i<m; i++){
		if(val[i]==n){
			rijesi(i);
		}
	}
	for(int i=0; i<m; i++){
		if(sol[U.parent[i]]){
			cout << "K" << sol[U.parent[i]] << '\n';
		}
		else{
			cout << "?" << '\n';
		}
	}
	return 0;
}

Compilation message (stderr)

kovanice.cpp: In member function 'void union_find::update(int, int)':
kovanice.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<komp[x].size(); i++){
                ~^~~~~~~~~~~~~~~
kovanice.cpp: In function 'int dfs(int)':
kovanice.cpp:55:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<U.komp[x].size(); i++){
               ~^~~~~~~~~~~~~~~~~
kovanice.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<ms[U.komp[x][i]].size(); j++){
                ~^~~~~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'void rijesi(int)':
kovanice.cpp:70:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<U.komp[x].size(); i++){
               ~^~~~~~~~~~~~~~~~~
kovanice.cpp:71:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0; j<ms[U.komp[x][i]].size(); j++){
                ~^~~~~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:101:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(pos<s.size()){
         ~~~^~~~~~~~~

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