oj.uz

답안 #846341

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
846341 2023-09-07T13:46:47 Z vjudge1 KOVANICE (COI15_kovanice) C++17
60 / 100
 2000 ms 17484 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--;

		cerr << a << " " << c << " " << b << "\n";

		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 << "?\n";
		else
			cout << "K" << t << "\n";
	}

}

Compilation message

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 348 KB Output is correct
2 Correct 14 ms 348 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 810 ms 17352 KB Output is correct
2 Correct 791 ms 17484 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 692 ms 4028 KB Output is correct
2 Correct 699 ms 4028 KB Output is correct
3 Correct 699 ms 4140 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2055 ms 12796 KB Time limit exceeded
2 Halted 0 ms 0 KB -