#include <bits/stdc++.h>
#define min(x,y) (x>=y?y:x)
#define max(x,y) ((x)>=(y)?(x):(y))
#define xc3(x) (x*(x-1)*(x-2)/6)
#define xc2(x) (x*(x-1)/2)
#define GF G[node][i].first
#define s0b stk[0].begin()
#define s0e stk[0].end()
#define s1b stk[1].begin()
#define s1e stk[1].end()
using namespace std;
#define ll long long
#define ull unsigned long long
int N,M,V;
vector<int> type;
vector<vector<int>> adjlistGEQ,adjlistGBYKTR;
vector<int> par,sizev;
int finds(int a){
if(a==par[a])return a;
return par[a] = finds(par[a]);
}
void make_union(int a,int b){
a=finds(a);
b=finds(b);
if(a!=b){
if(sizev[a]<sizev[b]){
swap(a,b);
}
par[b]=a;
sizev[a]+=sizev[b];
}
}
void PAL(int node,int deg){
int p = par[node];
for(int i=0;i<M;i++){
if(par[i]!=p)continue;
type[i]=N-deg+1;
}
}
bool DFS(int deg,int node){
if(type[node]==deg)return true;
if(deg==N){PAL(node,deg);return true;}
for(int i=0;i<adjlistGBYKTR[node].size();i++){
bool c = DFS(deg+1,adjlistGBYKTR[node][i]);
if(c && type[node]==-1)PAL(node,deg);
}
return (type[node]==deg);
}
int main()
{
cin>>N>>M>>V;
type.assign(M,-1);
vector<int> countt(M,0);
adjlistGEQ = adjlistGBYKTR = vector<vector<int>>(M,vector<int>(0));
par = vector<int>(M);iota(par.begin(),par.end(),0);
sizev = vector<int>(M,1);
for(int i=0;i<V;i++){
string s;cin>>s;
vector<string> a(2,"");int w=0;char t='c';
for(int j=0;j<s.size();j++){
if(s[j]=='=' || s[j]=='<'){
w++;
t=s[j];
}
else a[w]+=s[j];
}
int i1=stoi(a[0]),i2=stoi(a[1]);i1--;i2--;
if(t=='='){
adjlistGEQ[i1].push_back(i2);
adjlistGEQ[i2].push_back(i1);
make_union(i1,i2);
}
else{
adjlistGBYKTR[i2].push_back(i1);
countt[i1]++;
}}
for(int i=0;i<M;i++){
if(countt[i]!=0)continue;
DFS(1,i); // deg , node , parent
}
for(int i=0;i<M;i++){
if(type[i]==-1)cout<<"?"<<endl;
else{
cout<<"K"<<type[i]<<endl;
}
}
}
Compilation message
kovanice.cpp: In function 'bool DFS(int, int)':
kovanice.cpp:44:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i=0;i<adjlistGBYKTR[node].size();i++){
| ~^~~~~~~~~~~~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'int main()':
kovanice.cpp:62:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int j=0;j<s.size();j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2021 ms |
17592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2033 ms |
1872 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
32840 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
