oj.uz

Submission #965560

# Submission time Handle Problem Language Result Execution time Memory
965560 2024-04-18T22:05:34 Z nvujica KOVANICE (COI15_kovanice) C++14
10 / 100
 163 ms 40024 KB 
#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 = 0;
		
		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++){
//		cout << i << ' ' << par[i] << endl;
//	}
	
	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

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:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |   for(int j = 0; j < manji[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 22876 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 29776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23896 KB Output is correct
2 Correct 14 ms 24668 KB Output is correct
3 Correct 14 ms 24664 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 163 ms 40024 KB Output isn't correct
2 Halted 0 ms 0 KB -