oj.uz

Submission #846342

# Submission time Handle Problem Language Result Execution time Memory
846342 2023-09-07T13:47:19 Z vjudge1 KOVANICE (COI15_kovanice) C++17
100 / 100
 242 ms 29696 KB 
#include <bits/stdc++.h>

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

};


int 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[b] = 0;
		graph[a].push_back(b);
	}

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

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

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

	function< void(int, int) > settype = [&](int node, int tip){
		if( longest_path_below[node] + tip < n )
			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++)
		settype(equal[i], 1);

	for(int i=0; i<m; i++){
		int t = type[equal[i]];
		if(t==-1)
			cout << "?\n";
		else
			cout << "K" << t << "\n";
	}

}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 11124 KB Output is correct
2 Correct 78 ms 11256 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1732 KB Output is correct
2 Correct 36 ms 1784 KB Output is correct
3 Correct 37 ms 1564 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 20160 KB Output is correct
2 Correct 200 ms 20128 KB Output is correct
3 Correct 192 ms 19648 KB Output is correct
4 Correct 241 ms 22800 KB Output is correct
5 Correct 242 ms 29696 KB Output is correct