Submission #31155

#	Time	Username	Problem	Language	Result	Execution time	Memory
31155		pasa3232	Dreaming (IOI13_dreaming)	C++14	100 / 100	123 ms	16344 KiB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
const int INF=1987654321;

int n, m, l, cnt, ch[100010], M[2][100010], D[100010], A[100010];
struct C{
    int r, l;
    bool operator<(const C &a)const{
        return a.r>r;
    }
}data[100010];
vector<pair<int, int> > v[100010];

void dfs(int x){
    ch[x]=1;
    for(int i=0; i<v[x].size(); i++){
        int u=v[x][i].first;
        if(ch[u]==0){
            dfs(u);
            if(M[0][x]<v[x][i].second+M[0][u]){
                M[1][x]=M[0][x];
                M[0][x]=v[x][i].second+M[0][u];
            }
            else if(M[1][x]<v[x][i].second+M[0][u]){
                M[1][x]=M[0][u]+v[x][i].second;
            }
            D[x]=max(D[x], D[u]);
        }
    }
    D[x]=max(D[x], M[0][x]+M[1][x]);
}

void dfs1(int x, int len, int y, int inx){
    ch[x]=0;
    if(M[0][x]+len==D[y]){
        if(abs(M[0][x]-len)<data[inx].r-data[inx].l){
            data[inx].r=max(M[0][x], len);
            data[inx].l=min(M[0][x], len);
        }
    }
    if(M[0][x]+M[1][x]==D[y]){
        if(abs(M[0][x]-M[1][x])<data[inx].r-data[inx].l){
            data[inx].r=max(M[0][x], M[1][x]);
            data[inx].l=min(M[0][x], M[1][x]);
        }
    }
    for(int i=0; i<v[x].size(); i++){
        int u=v[x][i].first;
        if(ch[u]==1){
            if(v[x][i].second+M[0][u]==M[0][x]) dfs1(u, max(len+v[x][i].second, M[1][x]+v[x][i].second), y, inx);
            else dfs1(u, max(len+v[x][i].second, M[0][x]+v[x][i].second), y, inx);
        }
    }
}

int travelTime(int N, int M, int L, int K[], int B[], int T[]){
    n=N, m=M, l=L;
    for(int i=0; i<m; i++){
        int a=K[i], b=B[i], c=T[i];
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    for(int i=0; i<n; i++){
        if(ch[i]==0){
            dfs(i);
            A[cnt++]=i;
        }
    }
    for(int i=0; i<cnt; i++){
        data[i].r=INF;
        data[i].l=0;
        dfs1(A[i], 0, A[i], i);

    }
    sort(data, data+cnt);
    if(cnt==1) return data[0].r+data[0].l;
    else if(cnt==2) return max(data[0].r+data[0].l, max(data[1].r+data[1].l, data[0].r+data[1].r+l));
    else{
        int ans=0;
        for(int i=0; i<cnt; i++) ans=max(ans, data[i].r+data[i].l);
        return max(ans, max(data[cnt-1].r+data[cnt-2].r+l, data[cnt-2].r+data[cnt-3].r+l+l));
    }
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int)':
dreaming.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].size(); i++){
                  ~^~~~~~~~~~~~
dreaming.cpp: In function 'void dfs1(int, int, int, int)':
dreaming.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<v[x].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