Submission #846157

#	Time	Username	Problem	Language	Result	Execution time	Memory
846157		vjudge1	KOVANICE (COI15_kovanice)	C++17	0 / 100	255 ms	23404 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()

int main(){
	int n, m, k;
	cin>>n>>m>>k;

	vector<vector<pair<int, int>>> g(m);
	vector<int> src(m, 1), ans(m);
	for(int i=0; i<k; i++){
		int a, c;
		char b;
		cin>>a>>b>>c;
		a--; c--;

		if(b=='='){
			g[a].push_back({c, 0});
			g[c].push_back({a, 0});
		}
		else if(b=='<'){
			g[a].push_back({c, 1});
			src[c]=0;
		}
		else{
			g[c].push_back({a, 1});
			src[a]=0;
		}
	}

	queue<pair<int, int>> q;
	for(int i=0; i<m; i++) if(src[i])
		q.push({i, 1});
	
	vector<pair<int, int>> tmp;
	while(q.size()){
		auto[v, d]=q.front();
		q.pop();

		if(ans[v]) continue;

		ans[v]=d;
		tmp.push_back({d, v});
		for(auto [ch, e]:g[v]) q.push({ch, d+e});
	}

	sort(all(tmp), greater<pair<int, int>>());
	for(auto [cur, i]:tmp){
		if(cur==n) continue;
		bool f=0;
		for(auto [ch, e]:g[i]){
			if(e) f=1;
			if(ans[ch]!=cur+e) ans[i]=-1;
		}
		if(!f) ans[i]=-1;
	}

	for(int e:ans){
		if(e==-1) cout<<"?\n";
		else cout<<'K'<<e<<endl;
	}
}

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