제출 #284391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
284391		Ruba_K	꿈 (IOI13_dreaming)	C++14	0 / 100	57 ms	11384 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>

using namespace std ;

const int NN = 1e5 + 5 ;
vector<pair<int , int > > adj[NN];
int cmp[2] , vis[NN] ;
long long mn[2];

int summ = 0 , vid ;
void dfs(int u , int id){
    vis[u] = vid;

    for(auto f : adj[u]){
        if(vis[f.first] == vid)
            continue ;

        if(id + 1)mn[id] = min(mn[id] , max(1ll*summ , 1ll*cmp[id] - summ));
        summ += f.second ;
        dfs(f.first , id);
    }

}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    long long sum = 0 ;
    mn[0] = mn[1] = 1e18 ;


    for(int i = 0 ; i < M ; i ++){
        sum += T[i] ;
        adj[A[i]].push_back({B[i] , T[i]});
        adj[B[i]].push_back({A[i] , T[i]});
    }

    vid++;
    dfs(1 , -1);

    cmp[0] = summ ;
    cmp[1] = sum - cmp[0];

    summ = 0 ;
    vid ++ ;
    int d = 0 ;
    for(int i = 0 ; i < N ; i++){
        if(vis[i] != vid)dfs(i , d++) , summ = 0;
    }
    return mn[0] + mn[1] + L ;

}

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