Submission #1111260

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111260		nikolashami	Dreaming (IOI13_dreaming)	C++17	100 / 100	92 ms	16560 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+4;
vector<array<int,2>>adj[N];
int d[N][2],vis[N],wd;
vector<int>comp;

void build(int u,int p){
	comp.push_back(u);
	for(auto&[v,w]:adj[u]){
		if(!(v^p))
			continue;
		build(v,u);
	}
}

void unq(vector<int>&v){
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}

void dfs(int u,bool x){
	vis[u]=1;
	for(auto&[v,w]:adj[u]){
		if(vis[v])
			continue;
		d[v][x]=d[u][x]+w;
		dfs(v,x);
	}
}

int findmxlen(int node){
	comp.clear();
	build(node,0);
	unq(comp);

	d[node][0]=0;
	dfs(node,0);

	int mx=-1,kraj1,kraj2;
	for(int u:comp){
		if(d[u][0]>mx){
			mx=d[u][0];
			kraj1=u;
		}
		vis[u]=0;
	}

	d[kraj1][0]=0;
	dfs(kraj1,0);

	mx=-1;
	for(int u:comp){
		if(d[u][0]>mx){
			mx=d[u][0];
			kraj2=u;
		}
		vis[u]=0;
	}

	d[kraj2][1]=0;
	dfs(kraj2,1);

	int ret=1e9;

	for(int u:comp){
		ret=min(ret,max(d[u][0],d[u][1]));
		vis[u]=1;
	}

	wd=max(wd,d[kraj2][0]);

	return ret;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    int n=N,m=M,l=L;

    for(int i=0,u,v,w;i<m;++i){
        u=A[i];
        v=B[i];
        w=T[i];
        ++u,++v;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }

    fill(vis,vis+n+2,0);
    vector<int>poludijametri;

    for(int i=1;i<=n;++i){
        if(vis[i])
            continue;
        poludijametri.push_back(findmxlen(i));
    }

    sort(poludijametri.rbegin(),poludijametri.rend());

    int ans=wd;

    if(poludijametri.size()>1)
    	ans=max(ans,poludijametri[0]+poludijametri[1]+l);

    if(poludijametri.size()>2)
    	ans=max(ans,poludijametri[1]+poludijametri[2]+2*l);

    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int findmxlen(int)':
dreaming.cpp:53:5: warning: 'kraj1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   53 |  dfs(kraj1,0);
      |  ~~~^~~~~~~~~

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