// 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(x == y){
return;
}
if(siz[x] < siz[y]){
swap(x, y);
}
pa[y] = x, siz[x] += siz[y];
}
int dfs(int node, int dad){
int mx = 0;
for(int i = 0; i < adj[node].sz; i++){
if(adj[node][i] == dad){
continue;
}
dfs(adj[node][i], node);
mx = max(mx, subtree_size[adj[node][i]]);
}
for(int i = 0; i < adj[node].sz; i++){
if(adj[node][i] == dad){
continue;
}
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++){
pa[i] = i;
siz[i] = 1;
ans[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++){
int x = find(i);
if(radj[x].empty() && !vis[x]){
vis[x] = 1;
if(dfs(x, x) == n){
dfs2(x);
}
}
}
for(int i = 1; i <= m; i++){
int x = find(i);
if(ans[x] == -1){
cout << "?" << endl;
}
else{
cout << "K" << ans[x] << 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, long long int)':
kovanice.cpp:37: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]
37 | for(int i = 0; i < adj[node].sz; i++){
| ^
kovanice.cpp:44: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]
44 | for(int i = 0; i < adj[node].sz; i++){
| ^
kovanice.cpp: In function 'void dfs2(long long int)':
kovanice.cpp:56: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]
56 | for(int i = 0; i < pa2[node].sz; i++){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
268 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
270 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2051 ms |
33992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
289 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
