Submission #846336

#	Time	Username	Problem	Language	Result	Execution time	Memory
846336		vjudge1	KOVANICE (COI15_kovanice)	C++17	10 / 100	322 ms	28408 KiB

kovanice

#include <bits/stdc++.h>

#define int long long

using namespace std;

struct dsu{
	int len;
	vector<int> parent;
	dsu(int ln): len(ln), parent(ln,-1) {

		for(int i=0; i<ln; i++)
			parent[i] = i;

	}

	void connect(int a, int b){
		a = (*this)[a];
		b = (*this)[b];

		if(a>b)
			a^=b^=a^=b;

		parent[b] = a;

	}

	int operator[](int x) {
		if( parent[x] != x )
			return parent[x] = (*this)[parent[x]];
		return x;
	}

};


signed main(){

	int n,m,v;
	cin >> n >> m >> v;

	vector<pair<int,int>> less;

	dsu equal(m), grup(m);

	while(v--){
		int a,b;
		char c;

		cin >> a >> c >> b;
		a--;
		b--;

		grup.connect(a,b);

		if(c == '='){
			equal.connect(a,b);
		}else{
			less.push_back({a,b});
		}

	}

	vector<int> type(m, -1), root(m, 1);

	vector<vector<int>> graph(m);

	for(auto [a, b]: less){
		a = equal[a];
		b = equal[b];

		assert(a != b);

		root[a] = 0;
		graph[b].push_back(a);
	}

	vector<int> longest_path_below(m, -1);

	function<int(int)> dfs = [&](int node){

		int lpb = longest_path_below[node];
		
		if(lpb != -1)
			return lpb;
		
		for(int i=0; i<graph[node].size(); i++)
			lpb = max(lpb, dfs(graph[node][i]));
		
		return longest_path_below[node] = lpb+1;
	};

	for(int i=0; i<m; i++)
		dfs(equal[i]);

	function< void(int, int) > settype = [&](int node, int tip){
		assert(tip>0);

		if( longest_path_below[node] +1 != tip )
			return;
		if( type[node] != -1 )
			return;

		type[node] = tip;

		for(int i=0; i<graph[node].size(); i++)
			settype( graph[node][i], tip-1 );
	};

	for(int i=0; i<m; i++){
		if(root[equal[i]])
			settype(equal[i], n);
	}

	for(int i=0; i<m; i++){
		int t = type[equal[i]];

//		cout << longest_path_below[equal[i]] << " ";

		if(t==-1)
			cout << "K?\n";
		else
			cout << "K" << t << "\n";
	}

}

Compilation message (stderr)

kovanice.cpp: In lambda function:
kovanice.cpp:87:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |   for(int i=0; i<graph[node].size(); i++)
      |                ~^~~~~~~~~~~~~~~~~~~
kovanice.cpp: In lambda function:
kovanice.cpp:106:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |   for(int i=0; i<graph[node].size(); i++)
      |                ~^~~~~~~~~~~~~~~~~~~

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