제출 #846342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
846342		vjudge1	KOVANICE (COI15_kovanice)	C++17	100 / 100	242 ms	29696 KiB

kovanice

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

}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 40 / 40
• Subtask 3: 10 / 10
• Subtask 4: 40 / 40