제출 #590446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
590446		APROHACK	꿈 (IOI13_dreaming)	C++14	47 / 100	73 ms	19140 KiB

dreaming

#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 | }
      | ^

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23