oj.uz

답안 #965567

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965567 2024-04-18T22:20:29 Z nvujica KOVANICE (COI15_kovanice) C++14
100 / 100
 185 ms 48468 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 = e[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] || d[x2] != d[x] - 1) 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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 22876 KB Output is correct
2 Correct 7 ms 22956 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 29472 KB Output is correct
2 Correct 51 ms 29524 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 24152 KB Output is correct
2 Correct 14 ms 24156 KB Output is correct
3 Correct 15 ms 24156 KB Output is correct

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 185 ms 39508 KB Output is correct
2 Correct 154 ms 43132 KB Output is correct
3 Correct 141 ms 42804 KB Output is correct
4 Correct 114 ms 41584 KB Output is correct
5 Correct 139 ms 48468 KB Output is correct