Submission #590994

#	Time	Username	Problem	Language	Result	Execution time	Memory
590994		APROHACK	Dreaming (IOI13_dreaming)	C++14	100 / 100	86 ms	19144 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
    ll mxx = 0, largo = 0;
    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);
            if(largo < max(dist1, dist2)){
                largo = max(dist1, dist2);
                mxx=arboles.size();
            }
            arboles.PB({{dist1, dist2}, centro});

            //cout<<"cc"<<dist1<<" "<<dist2<<" "<<centro<<endl;
        }
    }
    ll centro1=arboles[mxx].S, distA=arboles[mxx].F.F, distB=arboles[mxx].F.S;
    ll centro2, distX, distY;
    for(int i = 0 ; i < arboles.size() ; i++){
        if(i==mxx)continue;
        //cout<<centro1<<" "<<distA<<" "<<distB<<endl;
        centro2=arboles[i].S, distX=arboles[i].F.F, distY=arboles[i].F.S;
        ll unir = L+max(distA, distB)+max(distX, distY);
        //ll ncentro = max(distA, distB)>max(distX, distY) ? centro1 : centro2;
        if(max(distA+distB, distX+distY)>unir){
            if((distA+distB>distX+distY)){
                //no hay cambio
            }else{
                centro1=centro2;
                distA=distX;
                distB=distY;
            }
        }else{
            if(max(distA, distB)>max(distX, distY)){
                if(distA<distB)swap(distA, distB);
                distB=L+max(distX, distY);
            }else{
                if(distA<distB)swap(distA, distB);
                distA+=L;
                distB=max(distX, distY);
                centro1 = centro2;
            }
        }

    }
    //cout<<centro1<<" "<<distA<<" "<<distB<<endl;
    return distA+distB;
}


/*
int main(){
    freopen("input.txt", "r", stdin);
    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;
}
*/

Compilation message (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:85:16: warning: unused variable 'B' [-Wunused-variable]
   85 |             ll B = nodox;
      |                ^
dreaming.cpp:88:16: warning: unused variable 'C' [-Wunused-variable]
   88 |             ll C = findCentro(A, 0);
      |                ^
dreaming.cpp:100: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]
  100 |     for(int i = 0 ; i < arboles.size() ; i++){
      |                     ~~^~~~~~~~~~~~~~~~
dreaming.cpp:98:8: warning: variable 'centro1' set but not used [-Wunused-but-set-variable]
   98 |     ll centro1=arboles[mxx].S, distA=arboles[mxx].F.F, distB=arboles[mxx].F.S;
      |        ^~~~~~~
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: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23