Submission #234019

#	Time	Username	Problem	Language	Result	Execution time	Memory
234019		Fasho	Dreaming (IOI13_dreaming)	C++14	100 / 100	98 ms	21240 KiB

dreaming

#include<bits/stdc++.h>
#include"dreaming.h"
#define f first
#define s second
 
using namespace std;
 
const int N = 2e5 + 500;
typedef pair<int, int> ipair;
int n , m , L;
vector<ipair> adj[N];
int dpD[N] , dpU[N] , dpD1[N] , dpD2[N];
bool vis[N];
vector<int> dist;
int ans;
int MN = 2e9 + 5;
 
void dfsU(int u , int p){
    for(ipair x : adj[u]){
        int v = x.f , w = x.s;
        if(v == p) continue;
        dpU[v] = dpU[u] + w;
        if(dpD[v] + w == dpD1[u]){
            if(dpD2[u] != -1) dpU[v] = max(dpU[v] , dpD2[u] + w);
        } else dpU[v] = max(dpU[v] , dpD1[u] + w);
        dfsU(v , u);
    }
    MN = min(MN , max(dpD[u] , dpU[u]));
    ans = max(ans , dpD[u] + dpU[u]);
}
void dfsD(int u , int BOSS){
    vis[u] = 1;
    for(ipair x : adj[u]){
        int v = x.f , w = x.s;
        if(vis[v]) continue;
        dfsD(v , BOSS);
        dpD[u] = max(dpD[u] , dpD[v] + w);
        if(dpD2[u] < dpD[v] + w){dpD2[u] = dpD[v] + w; if(dpD2[u] > dpD1[u])swap(dpD2[u] , dpD1[u]);};
    }
    if(u == BOSS) dfsU(u ,-1);
}
 
int travelTime(int N , int M , int L , int A[] , int B[] , int C[]){
    n = N; m = M; L = L;
    for(int i = 0; i < m; ++i){
        adj[A[i]].emplace_back(B[i] , C[i]);
        adj[B[i]].emplace_back(A[i] , C[i]);
    }
    memset(dpD1 , -1 , sizeof(dpD1));
    memset(dpD2 , -1 , sizeof(dpD2));
    for(int i = 0; i < n; ++i){
        if(!vis[i]){
            dfsD(i , i);
            dist.emplace_back(MN);
            //cerr << MN << " mn " << endl;
            MN = 2e9;
        }
    }
    /*
    for(int i = 0; i < n; ++i){
        cerr << i << " i " << dpD[i] << " dpD " << dpU[i] << " dpU " << endl;
    }*/
    sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
    //for(int i = 0; i < dist.size(); ++i) cerr << dist[i] << " "; cerr << endl;
    if(dist.size() >= 2) ans = max(ans , dist[0] + dist[1] + L);
    if(dist.size() >= 3) ans = max(ans , dist[1] + dist[2] + 2 * L);
    return ans;
    //cerr << ans << "ans" << endl;
 
}

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