Submission #71287

#	Time	Username	Problem	Language	Result	Execution time	Memory
71287		tamtam	Dreaming (IOI13_dreaming)	C++14	100 / 100	157 ms	17912 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define F first
#define S second
typedef long long ll;
using namespace std;
int n,m,l;
int ans=0;
vector<pair<int,int> > v[100010];
vector<int> comp;
vector<int> cent;
int cc[100010];
pair<int,int> dep[100010];
int par[100010];
void dfscc(int nod,int pt,int c){
    par[nod]=pt;
    cc[nod]=c;
    for (int i=0;i<v[nod].size();i++){
        if (v[nod][i].F==pt)continue;
        dfscc(v[nod][i].F,nod,c);
    }
}
pair<int,int> dfsdia (int nod,int pt){
    pair<int,int> res={0,nod};
    for (int i=0;i<v[nod].size();i++){
        if (v[nod][i].F==pt)continue;
        pair<int,int> x=dfsdia(v[nod][i].F,nod);
        res=max(res,{x.F+v[nod][i].S,x.S});
    }
    return res;
}
int dia(int nod0){
    return dfsdia(dfsdia(nod0,-1).S,-1).F;
}
pair<int,int> dfsdep (int nod,int pt){
    pair<int,int> res={0,nod};
    for (int i=0;i<v[nod].size();i++){
        if (v[nod][i].F==pt)continue;
        pair<int,int> x=dfsdep(v[nod][i].F,nod);
        res=max(res,{x.F+v[nod][i].S,v[nod][i].F});
    }
    dep[nod]=res;
    return res;
}
int center (int nod0){

    dfsdep(nod0,-1);
    if (v[nod0].size()==0){
        return 0;
    }
    int mx=0;
    int nod=nod0;
    while (1){
        int nxt=dep[nod].S;
        int edge=0;
        int mx1=0;
        for (int i=0;i<v[nod].size();i++){
            if (v[nod][i].F==nxt){
                edge=v[nod][i].S;
                break;
            }
        }
        for (int i=0;i<v[nod].size();i++){
            if (v[nod][i].F==nxt||v[nod][i].F==par[nod])continue;
            mx1=max(mx1,dep[v[nod][i].F].F+v[nod][i].S);
            //cout <<mx<<endl;
        }
        mx1=max(mx,mx1);
        /*cout <<mx<<endl;
        cout <<dep[nod].F<<" = "<<dep[nod].S<<endl;
            cout <<dep[nxt].F<<" = "<<dep[nxt].S<<endl;
            cout <<nod<<" -- "<<nxt<<endl;
            cout <<mx<<" "<<mx1<<endl;

//        break;*/

        if (dep[nxt].F<=mx1+edge){
      /*      cout <<dep[nod].F<<" = "<<dep[nod].S<<endl;
            cout <<dep[nxt].F<<" = "<<dep[nxt].S<<endl;
            cout <<nod<<" -- "<<nxt<<endl;
            cout <<mx<<" "<<mx1<<endl;*/
            return min( max(dep[nod].F,mx) , max(mx1+edge,dep[nxt].F)  );
        }else {
            nod=nxt;
            mx=mx1+edge;
        }
    }
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    memset(cc,-1,sizeof cc);
    n=N;m=M;l=L;
    for (int i=0;i<m;i++){
        v[A[i]].push_back({B[i],T[i]});
        v[B[i]].push_back({A[i],T[i]});
    }
    for (int i=0;i<n;i++){
        if (cc[i]==-1){
            comp.push_back(i);
            dfscc(i,-1,i);
        }
    }

    for (int i=0;i<comp.size();i++){
        ans=max(ans,dia(comp[i]));
        //cout <<"---------------\n";
        cent.push_back(center(comp[i]));
        //cout <<cent[i]<<" "<<i<<endl;
    }
    //cout <<endl;
    sort(cent.begin(),cent.end());
    reverse(cent.begin(),cent.end());
    if (cent.size()<=1){
        return ans;
    }else {
        ans=max(ans,cent[0]+cent[1]+l);
        if (cent.size()>=3){
            ans=max(ans,cent[1]+cent[2]+l+l);
        }
    }
    return ans;
}

/*
int main (){
    int n,m,l;
    int a[100010];
    int b[100010];
    int t[100010];
    cin >>n>>m>>l;
    for (int i=0;i<m;i++){
        cin >>a[i]>>b[i]>>t[i];
    }
    cout <<travelTime(n,m,l,a,b,t)<<endl;
    return 0;
}
/*

12 8 2
0 8 4
8 2 2
2 7 4
5 11 3
5 1 7
1 3 1
1 9 5
10 6 3
*/

Compilation message (stderr)

dreaming.cpp:136:1: warning: "/*" within comment [-Wcomment]
 /*
  
dreaming.cpp: In function 'void dfscc(int, int, int)':
dreaming.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> dfsdia(int, int)':
dreaming.cpp:25:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'std::pair<int, int> dfsdep(int, int)':
dreaming.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<v[nod].size();i++){
                  ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int center(int)':
dreaming.cpp:57:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[nod].size();i++){
                      ~^~~~~~~~~~~~~~
dreaming.cpp:63:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0;i<v[nod].size();i++){
                      ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:103:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<comp.size();i++){
                  ~^~~~~~~~~~~~

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