Submission #745311

#	Time	Username	Problem	Language	Result	Execution time	Memory
745311		kkkkkkkk	Dreaming (IOI13_dreaming)	C++14	100 / 100	673 ms	31932 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

int n,m;
vector<pair<int,int> > G[100005];
int vis[100005];
int maks_dist,najoddaleceno_teme;
int ans;
map<pair<int,int>,int> edges;

void dfs(int teme,int dist,bool vis1[]){
    //cout << "teme=" << teme << " dist=" << dist << endl;
    bool sosedi=false;
    vis[teme]=1;
    vis1[teme]=1;
    for (int i=0;i<G[teme].size();i++){
        int next=G[teme][i].first,vreme=G[teme][i].second;
        if (!vis1[next]){
            sosedi=true;
            vis[next]=1;
            vis1[next]=1;
            dfs(next,dist+vreme,vis1);
        }
    }
    if (sosedi==false){
        if (dist>maks_dist)
            najoddaleceno_teme=teme,maks_dist=dist;
        return;
    }
}

vector<int> pat,dijametar_pat;
int d;

void dfs2(int teme,int dist,bool vis1[]){
    //cout << "teme=" << teme << " dist=" << dist << endl;
    bool sosedi=false;
    vis[teme]=1;
    vis1[teme]=1;
    for (int i=0;i<G[teme].size();i++){
        int next=G[teme][i].first,vreme=G[teme][i].second;
        if (!vis1[next]){
            sosedi=true;
            vis[next]=1;
            vis1[next]=1;
            pat.push_back(next);
            dfs2(next,dist+vreme,vis1);
            pat.pop_back();
        }
    }
    if (sosedi==false){
        if (dist>=maks_dist)
            maks_dist=dist,dijametar_pat=pat,ans=max(ans,dist),d=dist;
        return;
    }
}

vector<int> komponenta; //dist do najdalecno teme od centralnoto

void dijametar(int teme){
    maks_dist=0;
    najoddaleceno_teme=teme;
    bool vis1[n];
    memset(vis1,0,sizeof(vis1));
    dfs(teme,0,vis1);
    //cout << najoddaleceno_teme << endl;
    memset(vis1,0,sizeof(vis1));
    pat.clear();
    maks_dist=0;
    pat.push_back(najoddaleceno_teme);
    dfs2(najoddaleceno_teme,0,vis1);
    // for (int i=0;i<dijametar_pat.size();i++){
    //     cout << dijametar_pat[i] << " ";
    // }
    // cout << endl;
    int centralno_teme=dijametar_pat[0];
    int zbir=0;
    int razlika=INT_MAX;
    for (int i=1;i<dijametar_pat.size();i++){
        zbir+=edges[{dijametar_pat[i-1],dijametar_pat[i]}];
        int ostatok=d-zbir;
        if (abs(zbir-ostatok)<razlika){
            razlika=abs(zbir-ostatok);
            centralno_teme=dijametar_pat[i];
        }
    }
    //cout << "centralno_teme=" << centralno_teme << endl;
    memset(vis1,0,sizeof(vis1));
    maks_dist=0;
    najoddaleceno_teme=centralno_teme;
    dfs(centralno_teme,0,vis1);
    //cout << "najoddaleceno_teme=" << najoddaleceno_teme << " maks_dist=" << maks_dist << endl;
    komponenta.push_back(maks_dist);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n=N;
    m=M;
    for (int i=0;i<M;i++){
        G[A[i]].push_back({B[i],T[i]});
        G[B[i]].push_back({A[i],T[i]});
        edges[{A[i],B[i]}]=T[i];
        edges[{B[i],A[i]}]=T[i];
    }
    for (int i=0;i<N;i++){
        if (vis[i]==0)
            dijametar(i);
    }
    sort(komponenta.begin(),komponenta.end());
    reverse(komponenta.begin(),komponenta.end());
    if (komponenta.size()==1) return max(ans,komponenta[0]);
    if (komponenta.size()==2) return max(ans,komponenta[0]+komponenta[1]+L);
    ans=max(ans,komponenta[0]+komponenta[1]+L);
    return max(ans,komponenta[1]+komponenta[2]+2*L);
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, bool*)':
dreaming.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |     for (int i=0;i<G[teme].size();i++){
      |                  ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int, int, bool*)':
dreaming.cpp:42:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i=0;i<G[teme].size();i++){
      |                  ~^~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dijametar(int)':
dreaming.cpp:81:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i=1;i<dijametar_pat.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