Submission #101162

#	Time	Username	Problem	Language	Result	Execution time	Memory
101162		ansol4328	Dreaming (IOI13_dreaming)	C++11	100 / 100	175 ms	12536 KiB

dreaming

#include "dreaming.h"
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;
typedef pair<int,int> P;

int n, m, l;
vector<P> lst[100005];
int rd[100005], rcnt, diameter, dv;
int par[100005], dist[100005], res;
bool check[100005];

void dfs(int v, int prev, int d)
{
    dist[v]=d;
    par[v]=prev;
    if(d>diameter) diameter=d, dv=v;
    check[v]=true;
    for(int i=0 ; i<lst[v].size() ; i++)
    {
        int nxt=lst[v][i].first;
        int dst=lst[v][i].second;
        if(nxt!=prev) dfs(nxt,v,d+dst);
    }
}

void solve()
{
    for(int i=rcnt ; i>1 ; i--)
    {
        int val=rd[i]+rd[i-1]+l;
        if(val>res) res=val, rd[i-1]=max(rd[i],rd[i-1]+l);
        else break;
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
    n=N, m=M, l=L;
    for(int i=0 ; i<m ; i++)
    {
        int v1, v2, d;
        v1=A[i], v2=B[i], d=T[i];
        lst[v1].push_back(P(v2,d));
        lst[v2].push_back(P(v1,d));
    }
    for(int i=0 ; i<n ; i++)
    {
        if(!check[i])
        {
            rcnt++;
            diameter=-1, dv=0;
            dfs(i,-1,0);
            int v1=dv;
            diameter=-1;
            dfs(v1,-1,0);
            int v2=dv, gap=1e9+7;
            while(v2!=-1)
            {
                int val=abs(diameter-dist[v2]*2);
                if(val<gap)
                {
                    gap=val;
                    rd[rcnt]=max(diameter-dist[v2],dist[v2]);
                }
                v2=par[v2];
            }
            res=max(res,diameter);
        }
    }
    sort(rd+1,rd+1+rcnt);
    solve();
    return res;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, int, int)':
dreaming.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0 ; i<lst[v].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