oj.uz

Submission #231541

# Submission time Handle Problem Language Result Execution time Memory
231541 2020-05-13T23:35:04 Z nickmet2004 Dreaming (IOI13_dreaming) C++11
0 / 100
 1000 ms 18228 KB 
#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]);
    }
    dist.assign(n , 0);
    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;

}
/*
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> L;
    for(int i = 0; i < m; ++i){
        int u , v , w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    //dist.assign(n , 0);
    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());
    //int x = *max_element(an.begin() , an.end());
    //for(int i = 0; i < dist.size(); ++i) cerr << dist[i] << " "; cerr << endl;
    //cerr << ans << "ans" << 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);
    cout << ans;
    return 0;
}
*/

Compilation message

dreaming.cpp:93:5: warning: "/*" within comment [-Wcomment]
     /*

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 18228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 18228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 18228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 12424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 18228 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 18228 KB Time limit exceeded
2 Halted 0 ms 0 KB -