Submission #910034

#TimeUsernameProblemLanguageResultExecution timeMemory
910034PetrixNetwork (BOI15_net)C++17
100 / 100
641 ms61324 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define int long long vector<vector<int>> v; int frunza[500001],p[500001]; vector<pair<int,int>> rasp; int cnt; void dfs(int parinte,int nod){ p[nod]=cnt;cnt++; int aux=0,i; for(i=0;i<v[nod].size();i++){ if(v[nod][i]!=parinte){ dfs(nod,v[nod][i]); aux++; } } if(!aux) frunza[nod]=1; } signed main() { int n,i,a,b;cnt=0; cin>>n;v.resize(n+1); for(i=0;i<n-1;i++){ cin>>a>>b; v[a].push_back(b); v[b].push_back(a); } dfs(-1,1); for(i=1;i<=n;i++){ if((i==1 && v[1].size()==1) || frunza[i]) rasp.push_back({p[i],i}); } cout<<(1ll*rasp.size()+1)/2<<"\n"; sort(rasp.begin(),rasp.end()); for(i=0;i<(1ll*rasp.size()+1ll)/2ll;i++){ cout<<rasp[i].second<<" "<<rasp[i+(rasp.size()/2)].second<<"\n"; } return 0; }

Compilation message (stderr)

net.cpp: In function 'void dfs(long long int, long long int)':
net.cpp:16:14: 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]
   16 |     for(i=0;i<v[nod].size();i++){
      |             ~^~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:41:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
   41 |     for(i=0;i<(1ll*rasp.size()+1ll)/2ll;i++){
      |             ~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...