Submission #80197

#TimeUsernameProblemLanguageResultExecution timeMemory
80197fabjanmKOVANICE (COI15_kovanice)C++98
10 / 100
2048 ms16696 KiB
#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 (stderr)

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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...