oj.uz

Submission #249152

# Submission time Handle Problem Language Result Execution time Memory
249152 2020-07-14T12:35:25 Z vanic KOVANICE (COI15_kovanice) C++14
100 / 100
 333 ms 39160 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{
	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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25080 KB Output is correct
2 Correct 26 ms 25080 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 28544 KB Output is correct
2 Correct 125 ms 28664 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 25720 KB Output is correct
2 Correct 40 ms 26360 KB Output is correct
3 Correct 47 ms 26368 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 33788 KB Output is correct
2 Correct 255 ms 33400 KB Output is correct
3 Correct 240 ms 33272 KB Output is correct
4 Correct 234 ms 33912 KB Output is correct
5 Correct 333 ms 39160 KB Output is correct