Submission #846608

#	Time	Username	Problem	Language	Result	Execution time	Memory
846608		vjudge1	KOVANICE (COI15_kovanice)	C++17	0 / 100	22 ms	45656 KiB

kovanice

#include <bits/stdc++.h>
#include <vector>

using namespace std;

int N,M,V;

vector<vector<int>> parents;
vector<vector<int>> kids;
vector<vector<int>> peers;
vector<bool> visited_d;
vector<bool> visited_h;
vector<bool> visited_travel;
vector<int> coin_values;


int deep(int node){
	
	/*cout << "at d " << node << endl;
	
	for(int i=0; i<M; i++){
		cout << visited_d[i] << " ";
	}
	cout << endl;*/
	 
	visited_d[node] = true;
	int ans = 0;
	
	for(auto kid:kids[node]){
		if(visited_d[kid]){continue;}
		ans = max(ans,deep(kid)+1);
	}
	for(auto peer:peers[node]){
		if(visited_d[peer]){continue;}
		ans = max(ans,deep(peer));
	}
	
	return ans;
}

int height(int node){
	
	//cout << "at h " << node << endl;
	visited_h[node] = true;
	int ans = 0;
	
	for(auto parent:parents[node]){
		if(visited_h[parent]){continue;}
		ans = max(ans,height(parent)+1);
	}
	for(auto peer:peers[node]){
		if(visited_h[peer]){continue;}
		ans = max(ans,height(peer));
	}
	
	return ans;
}

void travel(int node, int point){
	
	visited_travel[node] = true;
	coin_values[node] = point;
	
	for(auto kid:kids[node]){
		if(visited_travel[kid]==true){continue;}
		travel(kid,point-1);
	}
	for(auto parent:parents[node]){
		if(visited_travel[parent]==true){continue;}
		travel(parent,point+1);
	}
	for(auto peer:peers[node]){
		if(visited_travel[peer]==true){continue;}
		travel(peer,point);
	}
}

int main(){


		
	cin >> N >> M >> V;
	coin_values.assign(M,-1);
	parents.resize(M,vector<int>());
	kids.resize(M),vector<int>();
	peers.resize(M,vector<int>());
	
	char c,o;
	int f,s;
	for(int i=0; i<V; i++){
		c = cin.get();
		c = cin.get();
		f = c-'0';
		o = cin.get();
		c = cin.get();
		s = c-'0';
		
		f--;
		s--;
		
		if(o=='<'){parents[f].push_back(s);kids[s].push_back(f);}
		if(o=='>'){parents[s].push_back(f);kids[f].push_back(s);}
		if(o=='='){peers[f].push_back(s);peers[s].push_back(f);}
	}
	
	/*for(int i=0; i<M; i++){
		for(auto it:parents[i]){
			cout << it << " ";
		}
		cout << endl;
	}
	cout << "------------------" << endl;
	for(int i=0; i<M; i++){
		for(auto it:kids[i]){
			cout << it << " ";
		}
		cout << endl;
	}
	cout << endl;*/
	
	visited_d.assign(M,0);
	visited_h.assign(M,0);
	visited_travel.assign(M,0);
	for(int i=0; i<M; i++){
		if(visited_d[i] || visited_h[i]){continue;}
		int depth = deep(i);
		int h = height(i);
		
		//cout << "dh " << i << " " << depth << " " << h << endl;
		int diameter = depth+h+1;
		if(diameter==N){
			travel(i,depth);
		}
	}
	
	
	for(int i=0; i<M; i++){
		if(coin_values[i]==-1){cout << "?" << endl; continue;}
		cout << "K" << 1+coin_values[i] << endl;
	}
	
}

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