#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<iomanip>
#include<cstring>
using namespace std;
int n,m,v;
int brcv=0;
vector<pair<int,int> >jed;
vector<pair<pair<int,int>,char> >raz;
int mapa[300050];
int parent[300500];
vector<int> sus[300500];
int sol[300500];
vector<int>koji;
bool uz[300500];
vector<int>koj;
void input(){
cin>>n>>m>>v;
int br1,br2;
char zn;
for(int i=0;i<v;i++){
cin>>br1>>zn>>br2;
if(zn=='=')jed.push_back(make_pair(min(br1,br2),max(br1,br2)));
else raz.push_back(make_pair(make_pair(br1,br2),zn));
}
}
void rek(int cvor, int br){
bool soll=0;
//cout<<cvor<<" "<<pros<<endl;
if(br==n){
sol[cvor]=1;
uz[cvor]=true;
koj.push_back(cvor);
//return 1;
return;
}
else if(sus[cvor].size()==0)return;
for(int i=0;i<sus[cvor].size();i++) rek(sus[cvor][i], br+1);
//cout<<cvor<<endl;
if(koj.size()>0 && uz[koj.front()]){
sol[cvor]=n-br+1;
uz[cvor]=true;
koj.push_back(cvor);
}
//return soll;
}
void solve(){
sort(jed.begin(),jed.end());
int oz=0;
for(int i=0;i<jed.size();i++){
int br1=jed[i].first;
int br2=jed[i].second;
if(mapa[br1]==0 && mapa[br2]==0){
oz++;
brcv++;
mapa[br1]=oz;
mapa[br2]=oz;
}
else if(mapa[br1]==0 && mapa[br2]!=0)mapa[br1]=mapa[br2];
else if(mapa[br1]!=0 && mapa[br2]==0)mapa[br2]=mapa[br1];
}
for(int i=0;i<raz.size();i++){
int br1=raz[i].first.first;
int br2=raz[i].first.second;
char zn=raz[i].second;
if(mapa[br1]==0){
oz++;
brcv++;
mapa[br1]=oz;
}
if(mapa[br2]==0){
oz++;
brcv++;
mapa[br2]=oz;
}
if(zn=='<'){
parent[mapa[br1]]=mapa[br2];
sus[mapa[br2]].push_back(mapa[br1]);
}
else{
parent[mapa[br2]]=mapa[br1];
sus[mapa[br1]].push_back(mapa[br2]);
}
}
/*cout<<endl;
for(int i=1;i<=m;i++)cout<<i<<" -----> "<<mapa[i]<<endl;
cout<<endl;*/
/*for(int i=1;i<=brcv;i++){
cout<<i<<" -> ";
for(int j=0;j<sus[i].size();j++)cout<<sus[i][j]<<" ";
cout<<endl;
}
cout<<11111111111<<" "<<sol[4]<<endl;*/
for(int i=1;i<=brcv;i++){
int cvor=i;
//cout<<cvor<<" "<<parent[cvor]<<endl;
if(parent[cvor]==0){
//cout<<cvor<<endl;
//cout<<cvor<<endl;
rek(cvor, 1);
//cout<<bl;
}
}
}
void print(){
//cout<<endl;
for(int i=1;i<=m;i++){
if(sol[mapa[i]] != 0)cout<<"K"<<sol[mapa[i]]<<endl;
else cout<<"?"<<endl;
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
input();
solve();
print();
return 0;
}
Compilation message
kovanice.cpp: In function 'void rek(int, int)':
kovanice.cpp:53:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<sus[cvor].size();i++) rek(sus[cvor][i], br+1);
~^~~~~~~~~~~~~~~~~
kovanice.cpp:43:10: warning: unused variable 'soll' [-Wunused-variable]
bool soll=0;
^~~~
kovanice.cpp: In function 'void solve()':
kovanice.cpp:66:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<jed.size();i++){
~^~~~~~~~~~~
kovanice.cpp:79:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<raz.size();i++){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
7544 KB |
Output is correct |
| 2 |
Correct |
11 ms |
7652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
405 ms |
12868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2041 ms |
12868 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2048 ms |
16696 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
