Submission #965555

#	Time	Username	Problem	Language	Result	Execution time	Memory
965555		nvujica	KOVANICE (COI15_kovanice)	C++14	0 / 100	149 ms	76156 KiB

kovanice

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second

using namespace std;

const int maxn = 3e5 + 10;

int n, m, v;
vector <int> jed[maxn];
vector <int> manji[maxn];
vector <int> e[maxn];
int par[maxn];
int d[maxn];
int ans[maxn];

void dfs(int x){
	for(int i = 0; i < jed[x].size(); i++){
		int x2 = jed[x][i];
		
		if(par[x2]) continue;
		
		par[x2] = par[x];
		dfs(x2);
	}
}

void rek(int x){
	d[x] = 1;
	
	for(int i = 0; i < e[x].size(); i++){
		int x2 = manji[x][i];
		
		if(!d[x2]) rek(x2);
		
		d[x] = max(d[x], d[x2] + 1);
	}
}

void dfs2(int x){
	ans[x] = d[x];
	
	for(int i = 0; i < e[x].size(); i++){
		int x2 = e[x][i];
		
		if(ans[x2]) continue;
		
		dfs2(x2);
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m >> v;
	
	for(int i = 0; i < v; i++){
		string s;
		cin >> s;
		
		int poz = -1;
		
		for(int j = 0; j < s.size(); j++){
			if(s[j] < '0' || s[j] > '9') poz = j;
		}
		
		int a = 0, b = 0;
		
		for(int j = 0; j < poz; j++){
			a *= 10;
			a += s[j] - '0';
		}
		
		for(int j = poz + 1; j < s.size(); j++){
			b *= 10;
			b += s[j] - '0';
		}
		
		if(s[poz] == '='){
			jed[a].push_back(b);
			jed[b].push_back(a);
		}
		else {
			manji[b].push_back(a);
		}
	}
	
	for(int i = 1; i <= m; i++){
		if(par[i]) continue;
		
		par[i] = i;
		dfs(i);
	}
	
	for(int i = 1; i <= m; i++){
		for(int j = 0; j < manji[i].size(); j++){
			e[par[i]].push_back(par[manji[i][j]]);
		}
	}

	
	for(int i = 1; i <= m; i++){
		if(d[i]) continue;
		
		rek(i);
	}
	
	for(int i = 1; i <= m; i++){
		if(d[i] == n) dfs2(i);
	}
	
	for(int i = 1; i <= m; i++){
		ans[i] = ans[par[i]];
	}
	
	for(int i = 1; i <= m; i++){
		if(ans[i]) cout << 'K' << ans[i] << "\n";
		else cout << "?\n";
	}
	
	return 0;
}

Compilation message (stderr)

kovanice.cpp: In function 'void dfs(int)':
kovanice.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < jed[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~~~
kovanice.cpp: In function 'void rek(int)':
kovanice.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < e[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
kovanice.cpp: In function 'void dfs2(int)':
kovanice.cpp:45:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(int i = 0; i < e[x].size(); i++){
      |                 ~~^~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:66:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int j = 0; j < s.size(); j++){
      |                  ~~^~~~~~~~~~
kovanice.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for(int j = poz + 1; j < s.size(); j++){
      |                        ~~^~~~~~~~~~
kovanice.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int j = 0; j < manji[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~

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