oj.uz

Submission #846315

# Submission time Handle Problem Language Result Execution time Memory
846315 2023-09-07T13:27:07 Z vjudge1 KOVANICE (COI15_kovanice) C++17
10 / 100
 250 ms 28224 KB 
#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;
		
		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] +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[i])
			settype(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

kovanice.cpp: In lambda function:
kovanice.cpp:88: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]
   88 |   for(int i=0; i<graph[node].size(); i++)
      |                ~^~~~~~~~~~~~~~~~~~~
kovanice.cpp: In lambda function:
kovanice.cpp:105: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]
  105 |   for(int i=0; i<graph[node].size(); i++)
      |                ~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 78 ms 15668 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3020 KB Output is correct
2 Correct 36 ms 3008 KB Output is correct
3 Correct 36 ms 3004 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 250 ms 28224 KB Output isn't correct
2 Halted 0 ms 0 KB -