제출 #846148

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

kovanice

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
int n,m,v,depth[N],ans[N];
vector < int > graph[N];
struct DSU{
	vector < int > par;
	DSU(int x){
		par.resize(x+1);
		iota(par.begin() , par.end() , 0);
	}
	int find(int a){
		if(par[a] == a)return a;
		return par[a] = find(par[a]);
	}
	void merge(int a, int b){
		par[find(a)] = find(b);
	}
} dsu(N);
int find_depth(int node){
	if(depth[node] != -1)return depth[node];
	depth[node] = 1;
	for(auto itr : graph[node]){
		if(itr == node)continue;
		depth[node] = max(depth[node] , find_depth(itr) + 1);
	}
	return depth[node];
}
void investigate(int node , int dist){
	if(ans[node] != -1)return;
	ans[node] = dist;
	for(auto itr : graph[node]){
		if(itr == node)continue;
		if(depth[itr] == (dist-1)){
			investigate(itr,dist-1);
		}
	}
}
void solve(){
	memset(ans , -1 , sizeof(ans));
	memset(depth , -1 , sizeof(depth));
	cin >> n >> m >> v;
	vector < array < int , 3 > > query;
	for(int i = 0;i<v;i++){
		string inp;
		cin >> inp;
		int u , sign , v;
		string bruh;
		int ind = 0;
		for(ind;ind<inp.size();ind++){
			if(inp[ind] >= '0' and inp[ind] <= '9')bruh += inp[ind];
			else break;
		}
		u = stoi(bruh);
		if(inp[ind] == '<')sign = 0;
		else if(inp[ind] == '>')sign = 1;
		else sign = 2;
		ind++;
		bruh = "";
		for(ind;ind<inp.size();ind++){
			if(inp[ind] >= '0' and inp[ind] <= '9')bruh += inp[ind];
			else break;
		}
		v = stoi(bruh);
		query.push_back({u,sign,v});
	}
	for(auto itr : query){
		if(itr[1] == 2){
			dsu.merge(itr[0],itr[2]);
		}
	}
	for(auto itr : query){
		int u = itr[0] , v = itr[2];
		if(itr[1] == 1){
			graph[dsu.find(u)].push_back(dsu.find(v));
			//cout << dsu.find(u) << " -> " << dsu.find(v) << endl;
		}
		else{
			graph[dsu.find(v)].push_back(dsu.find(u));
			//cout << dsu.find(v) << " -> " << dsu.find(u) << endl;
		}
	}
	for(auto &itr : graph){
		sort(itr.begin() , itr.end());
		itr.resize(unique(itr.begin() , itr.end()) - itr.begin());
	}
	for(int i = 1;i<=m;i++){
		find_depth(dsu.find(i));
	}
	for(int i = 1;i<=m;i++){
		if(depth[dsu.find(i)] == n){
			investigate(dsu.find(i),n);
		}
	}
	for(int i = 1;i<=m;i++){
		if(ans[dsu.find(i)] == -1)cout << '?' << endl;
		else cout << 'K' << ans[dsu.find(i)] << endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

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

kovanice.cpp: In function 'void solve()':
kovanice.cpp:50:7: warning: statement has no effect [-Wunused-value]
   50 |   for(ind;ind<inp.size();ind++){
      |       ^~~
kovanice.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(ind;ind<inp.size();ind++){
      |           ~~~^~~~~~~~~~~
kovanice.cpp:60:7: warning: statement has no effect [-Wunused-value]
   60 |   for(ind;ind<inp.size();ind++){
      |       ^~~
kovanice.cpp:60:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |   for(ind;ind<inp.size();ind++){
      |           ~~~^~~~~~~~~~~

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