제출 #590446

#제출 시각아이디문제언어결과실행 시간메모리
590446APROHACK꿈 (IOI13_dreaming)C++14
47 / 100
73 ms19140 KiB
#include <bits/stdc++.h> #include "dreaming.h" #define ll long long #define PB push_back #define F first #define S second using namespace std; const ll MAXN = 100001; bool recorrido[MAXN]; vector<pair<int, ll > >adj[MAXN]; vector<int>camino; ll maxtraveltime = 0, nodox; bool two = false; ll findlongest(int node, ll cur, int parent){ // cout<<node<<endl; recorrido[node]=true; int pp = 0; for(int i = 0 ;i < adj[node].size(); i++){ if(parent != adj[node][i].F){ if(findlongest(adj[node][i].F, cur+adj[node][i].S, node)){ camino.PB(node); //cout<<"added "<<node<<" "<<endl; if(two)pp++; } } } if(pp)return pp; if(cur>maxtraveltime){ maxtraveltime=cur; nodox=node; camino.PB(node); //cout<<node<<" "; return 1; } return 0; } ll centro, dist1, dist2, diff; ll findCentro(int node, int lleva){ //cout<<node<<" "<<lleva<<" "<<maxtraveltime-lleva<<endl; if(llabs((maxtraveltime-lleva) - lleva)<diff){ centro = node; diff=abs(lleva - (maxtraveltime-lleva)); dist1=lleva; dist2=maxtraveltime-lleva; } if(lleva > (maxtraveltime-lleva)){ return centro; } for(int i = 0 ;i < adj[node].size(); i++){ if(camino.back() == adj[node][i].F){ camino.pop_back(); return findCentro(adj[node][i].F, adj[node][i].S+lleva); } } } int travelTime(int N, int M, int L, int A[], int B[], int T[]) { for(int i = 0 ; i < M ; i ++){ adj[A[i]].PB({B[i], T[i]}); adj[B[i]].PB({A[i], T[i]}); } vector<pair<pair<ll, ll>, int> >arboles; //distA distB Centro for(int i = 0 ; i < N ; i++){ if(!recorrido[i]){ //cout<<"runnin"<<i<<endl; maxtraveltime=0; two=false; diff=LLONG_MAX; if(adj[i].size()==0){ arboles.PB({{0, 0}, i}); //cout<<"cc"<<0<<" "<<0<<" "<<i<<endl; continue; } findlongest(i, 0, -1); ll A = nodox; maxtraveltime = 0; two=true; findlongest(A, 0, -1); ll B = nodox; ////cout<<"mx"<<maxtraveltime<<endl; camino.pop_back(); ll C = findCentro(A, 0); arboles.PB({{dist1, dist2}, centro}); //cout<<"cc"<<dist1<<" "<<dist2<<" "<<centro<<endl; } } ll centro1=arboles[0].S, distA=arboles[0].F.F, distB=arboles[0].F.S; for(int i = 1 ; i < arboles.size() ; i++){ //cout<<centro1<<" "<<distA<<" "<<distB<<endl; ll unir = L+max(distA, distB)+max(arboles[i].F.F, arboles[i].F.S); ll ncentro = max(distA, distB)>max(arboles[i].F.F, arboles[i].F.S) ? centro1 : arboles[i].S; if(max(distA+distB, arboles[i].F.F+arboles[i].F.S)>unir){ if((distA+distB>arboles[i].F.F+arboles[i].F.S)){ //no hay cambio }else{ centro1=arboles[i].S; distA=arboles[i].F.F; distB=arboles[i].F.S; } }else{ if(max(distA, distB)>max(arboles[i].F.F, arboles[i].F.S)){ if(distA<distB)swap(distA, distB); distB=L+max(arboles[i].F.F, arboles[i].F.S); }else{ if(distA<distB)swap(distA, distB); distA+=L; distB=max(arboles[i].F.F, arboles[i].F.S); } centro1=ncentro; } } //cout<<centro1<<" "<<distA<<" "<<distB<<endl; return distA+distB; } /* int main(){ ll n, m, a, b , t, tt; cin>>n>>m>>tt; vector<int>A, B, T; for(int i = 0 ; i < m ; i++){ cin>>a>>b>>t; A.PB(a); B.PB(b); T.PB(t); } cout<<travelTime(n, m, tt, A.data(), B.data(), T.data())<<endl; } */

컴파일 시 표준 에러 (stderr) 메시지

dreaming.cpp: In function 'long long int findlongest(int, long long int, int)':
dreaming.cpp:18:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for(int i = 0 ;i  < adj[node].size(); i++){
      |                    ~~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int findCentro(int, int)':
dreaming.cpp:52:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 0 ;i  < adj[node].size(); i++){
      |                    ~~~^~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:84:16: warning: unused variable 'B' [-Wunused-variable]
   84 |             ll B = nodox;
      |                ^
dreaming.cpp:87:16: warning: unused variable 'C' [-Wunused-variable]
   87 |             ll C = findCentro(A, 0);
      |                ^
dreaming.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(int i = 1 ; i < arboles.size() ; i++){
      |                     ~~^~~~~~~~~~~~~~~~
dreaming.cpp: In function 'long long int findCentro(int, int)':
dreaming.cpp:58:1: warning: control reaches end of non-void function [-Wreturn-type]
   58 | }
      | ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...