// 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], vis2[N], ans[N], subtree_size[N];
int binpow(int a, int b){
int res = 1;
while(b){
if(b & 1) res *= a;
a *= a;
b >>= 1;
}
return res;
}
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){
vis2[node] = 1;
ans[node] = subtree_size[node];
for(int i = 0; i < pa2[node].sz; i++){
if(!vis2[pa2[node][i]]){
dfs2(pa2[node][i]);
}
}
}
inline void solve(){
int n, m, k;
cin >> n >> m >> k;
pair<char, pair<int, int> > 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++){
string s;
cin >> s;
vector<int> sayi1, sayi2;
int in = 0;
while(s[in] <= '9' && s[in] >= '0'){
sayi1.pb(s[in]-'0');
in++;
}
while(s[in] > '9' || s[in] < '0'){
a[i].ff = s[in];
in++;
}
while(in < s.sz){
sayi2.pb(s[in]-'0');
in++;
}
a[i].ss.ff = a[i].ss.ss = 0;
for(int j = 0; j < sayi1.sz; j++){
a[i].ss.ff += sayi1[j] * binpow(10, sayi1.sz - j - 1);
}
for(int j = 0; j < sayi2.sz; j++){
a[i].ss.ss += sayi2[j] * binpow(10, sayi2.sz - j - 1);
}
if(a[i].ff == '='){
merge(a[i].ss.ff, a[i].ss.ss);
}
}
for(int i = 0; i < k; i++){
int x = find(a[i].ss.ff), y = find(a[i].ss.ss);
if(a[i].ff == '='){
continue;
}
if(a[i].ff == '>'){
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]){
if(dfs(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)':
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: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 < adj[node].sz; i++){
| ^
kovanice.cpp: In function 'void dfs2(long long int)':
kovanice.cpp:60: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]
60 | for(int i = 0; i < pa2[node].sz; i++){
| ^
kovanice.cpp: In function 'void solve()':
kovanice.cpp:90:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while(in < s.sz){
| ^
kovanice.cpp:95:26: 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]
95 | for(int j = 0; j < sayi1.sz; j++){
| ^
kovanice.cpp:98:26: 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]
98 | for(int j = 0; j < sayi2.sz; j++){
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
31324 KB |
Output is correct |
| 2 |
Correct |
8 ms |
31324 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
296 ms |
42124 KB |
Output is correct |
| 2 |
Correct |
290 ms |
42016 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
31 ms |
36296 KB |
Output is correct |
| 2 |
Correct |
30 ms |
36316 KB |
Output is correct |
| 3 |
Correct |
32 ms |
36696 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
548 ms |
56096 KB |
Output is correct |
| 2 |
Correct |
547 ms |
55268 KB |
Output is correct |
| 3 |
Correct |
602 ms |
54940 KB |
Output is correct |
| 4 |
Correct |
794 ms |
61272 KB |
Output is correct |
| 5 |
Correct |
607 ms |
63436 KB |
Output is correct |
