// Aber der schlimmste Fiend, dem du begegnen kannst, wirst du immer dir selber sein
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#define int long long int
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define rev reverse
#define all(x) x.begin(),x.end()
#define acc accumulate
#define sz size()
#define MOD 998244353
#define rall(x) x.rbegin(),x.rend()
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const int N = 3e5 + 5;
vector<int> adj[N], radj[N], pa2[N];
int siz[N], pa[N], vis[N], ans[N], subtree_size[N];
int find(int n){
return ((pa[n] == n) ? n : (pa[n] = find(pa[n])));
}
void merge(int x, int y){
x = find(x), y = find(y);
if(siz[x] < siz[y]){
swap(x, y);
}
pa[y] = x, siz[x] += siz[y];
}
int dfs(int node){
vis[node] = 1;
int mx = 0;
for(int i = 0; i < adj[node].sz; i++){
if(!vis[adj[node][i]]){
dfs(adj[node][i]);
mx = max(mx, subtree_size[adj[node][i]]);
}
}
for(int i = 0; i < adj[node].sz; i++){
if(subtree_size[adj[node][i]] == mx){
pa2[node].emplace_back(adj[node][i]);
}
}
return subtree_size[node] = mx+1;
}
void dfs2(int node){
ans[node] = subtree_size[node];
for(int i = 0; i < pa2[node].sz; i++){
dfs2(pa2[node][i]);
}
}
inline void solve(){
int n, m, k;
cin >> n >> m >> k;
string a[k];
for(int i = 1; i <= m; i++){
ans[i] = -1;
}
for(int i = 1; i <= m; i++){
pa[i] = i;
siz[i] = 1;
}
for(int i = 0; i < k; i++){
cin >> a[i];
if(a[i][1] == '='){
merge(a[i][0]-'0', a[i][2]-'0');
}
}
for(int i = 0; i < k; i++){
int x = find(a[i][0]-'0'), y = find(a[i][2]-'0');
if(a[i][1] == '='){
continue;
}
if(a[i][1] == '>'){
swap(x, y);
}
radj[x].emplace_back(y);
adj[y].emplace_back(x);
}
for(int i = 1; i <= m; i++){
if(radj[find(i)].empty() && !vis[find(i)]){
if(dfs(find(i)) == n){
dfs2(find(i));
}
}
}
for(int i = 1; i <= m; i++){
if(ans[find(i)] == -1){
cout << "?" << endl;
}
else{
cout << "K" << ans[find(i)] << endl;
}
}
}
int32_t main(){
fast_io
int t;
t = 1;
while(t--) solve();
}
Compilation message
kovanice.cpp: In function 'long long int dfs(long long int)':
kovanice.cpp:35:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int i = 0; i < adj[node].sz; i++){
| ^
kovanice.cpp:41:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | for(int i = 0; i < adj[node].sz; i++){
| ^
kovanice.cpp: In function 'void dfs2(long long int)':
kovanice.cpp:50:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i = 0; i < pa2[node].sz; i++){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
29020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
234 ms |
38464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
35272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
351 ms |
48692 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
