Submission #12809

#	Time	Username	Problem	Language	Result	Execution time	Memory
12809		qja0950	Dreaming (IOI13_dreaming)	C++98	100 / 100	105 ms	8696 KiB

dreaming

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

using namespace std;

#define MAX_N 101101
typedef long long ll;

vector< pair<int, int> > V[MAX_N];
vector<int> RadSort;
queue<int> Q;

int Check[MAX_N];
int Dis[MAX_N];
int N, M, L;
int Ans;

int Find_Last(int first, int checkp) {
    ll LastDis = -1;
    int LastInd = -1;
    
    Check[first] = checkp;
    Dis[first] = 0;
    
    while(!Q.empty()) Q.pop();
    Q.push(first);
    
    while(!Q.empty()) {
        int now = Q.front(); Q.pop();
        for(int i=0; i<V[now].size(); i++) {
            int next = V[now][i].first;
            int cost = V[now][i].second;
            if(Check[next] == checkp) continue;
            Q.push(next);
            Check[next] = checkp;
            Dis[next] = Dis[now] + 1ll * cost;
        }
        if(Dis[now] > LastDis) {
            LastDis = Dis[now];
            LastInd = now;
        }
    }
    return LastInd;
}
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++) {
        V[b[i]].push_back( make_pair(a[i], t[i]) );
        V[a[i]].push_back( make_pair(b[i], t[i]) );
    }
    for(int i=0; i<N; i++) {
        Check[i] = 0;
        Dis[i] = 0;
    }
    
    for(int i=0; i<N; i++) {
        if(Check[i] != 0) continue;
        
        int fir = Find_Last(i  , 1);
        int sec = Find_Last(fir, 2);
        
        int dia = Dis[sec];
        int rad = dia;
        
        Ans = max(Ans, dia);
        
        for(int now = sec; now != fir;) {
            for(int i=0; i<V[now].size(); i++) {
                int next = V[now][i].first;
                int cost = V[now][i].second;
                
                if( (Dis[next] + cost) == Dis[now]) {
                    now = next;
                    break;
                }
            }
            int nowd = Dis[now];
            rad = min(rad, max(nowd, dia-nowd) );
        }
        RadSort.push_back(rad);
    }
    sort( RadSort.begin(), RadSort.end() );
    
    int RadS = (int)RadSort.size();
    if(RadS == 2) {
        int r0 = RadSort[RadS-1], r1 = RadSort[RadS-2];
        int now = r0 + r1 + L;
        Ans = max(Ans, now);
    }
    if(RadS >= 3) {
        int r0 = RadSort[RadS-1], r1 = RadSort[RadS-2], r2 = RadSort[RadS-3];
        int now = max(r0 + r1 + L, r1 + r2 + 2*L);
        Ans = max(Ans, now);
    }
    return Ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int Find_Last(int, int)':
dreaming.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0; i<V[now].size(); i++) {
                      ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:70:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0; i<V[now].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