Submission #80068

#TimeUsernameProblemLanguageResultExecution timeMemory
80068fabjanmKOVANICE (COI15_kovanice)C++98
0 / 100
2061 ms16648 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; void input(){ cin>>n>>m>>v; int br1,br2; char zn; string r; 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)); } } int rek(int cvor, int br){ if(br==n){ sol[cvor]=1; return 1; } else if(sus[cvor].size()==0)return 0; bool soll=0; for(int i=0;i<sus[cvor].size();i++) soll=soll || rek(sus[cvor][i], br+1); if(soll) sol[cvor]=n-br+1; 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]); } } /*for(int i=1;i<=brcv;i++)cout<<i<<" -> "<<parent[i]<<endl; cout<<endl<<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; }*/ for(int i=1;i<=brcv;i++){ int cvor=i; //cout<<cvor<<" "<<parent[cvor]<<endl; if(parent[cvor]==0){ //cout<<cvor<<endl; rek(cvor, 1); } } /*cout<<"size od koji je : "<<koji.size()<<endl; for(int i=0;i<koji.size();i++){ int br=1,cvor=koji[i]; for(int j=0;j<n;j++){ if(sol[cvor]!=0)break; sol[cvor]=br; cvor=parent[cvor]; br++; } }*/ ///for(int i=1;i<=m;i++)cout<<i<<" -> "<<mapa[i]<<endl; ///cout<<endl<<endl; ///for(int i=1;i<=brcv;i++)cout<<i<<" -> "<<parent[i]<<endl; //cout<<brcv<<endl; } void print(){ for(int i=1;i<=m;i++){ if(sol[mapa[i]] != 0)cout<<"K"<<sol[mapa[i]]<<endl; else cout<<"?"<<endl; } } int main(){ input(); solve(); print(); return 0; }

Compilation message (stderr)

kovanice.cpp: In function 'int rek(int, int)':
kovanice.cpp:47:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<sus[cvor].size();i++) soll=soll || rek(sus[cvor][i], br+1);
                 ~^~~~~~~~~~~~~~~~~
kovanice.cpp: In function 'void solve()':
kovanice.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<jed.size();i++){
                 ~^~~~~~~~~~~
kovanice.cpp:68: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...