Submission #745310

#	Time	Username	Problem	Language	Result	Execution time	Memory
745310		kkkkkkkk	Dreaming (IOI13_dreaming)	C++14	Compilation error	0 ms	0 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);
}
    
int main(){
    int N=12,M=8,L=2,A[]={0,8,2,5,5,1,1,10},B[]={8,2,7,11,1,3,9,6},T[]={4,2,4,3,7,1,5,3};
    cout << travelTime(N,M,L,A,B,T);
    return 0;
}

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++){
      |                  ~^~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccpbgMTU.o: in function `main':
dreaming.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc7Pw7AW.o:grader.c:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status