oj.uz

Submission #231537

# Submission time Handle Problem Language Result Execution time Memory
231537 2020-05-13T23:01:30 Z nickmet2004 Dreaming (IOI13_dreaming) C++11
0 / 100
 72 ms 16888 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);
    }
    if(MN > max(dpD[u] , dpU[u])){
        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;
    //cerr << ans << "ans" << endl;
    return max({dist[0] + dist[1] + L , dist[1] + dist[2] + L + L , ans});
}
/*
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());
    //for(int i = 0; i < dist.size(); ++i) cerr << dist[i] << " "; cerr << endl;
    //cerr << ans << "ans" << endl;
    cout <<  max({dist[0] + dist[1] + L , dist[1] + dist[2] + L + L , 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 Correct 62 ms 16888 KB Output is correct
2 Correct 72 ms 16888 KB Output is correct
3 Correct 49 ms 15224 KB Output is correct
4 Correct 16 ms 8192 KB Output is correct
5 Correct 14 ms 7552 KB Output is correct
6 Correct 21 ms 8960 KB Output is correct
7 Incorrect 8 ms 6656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16888 KB Output is correct
2 Correct 72 ms 16888 KB Output is correct
3 Correct 49 ms 15224 KB Output is correct
4 Correct 16 ms 8192 KB Output is correct
5 Correct 14 ms 7552 KB Output is correct
6 Correct 21 ms 8960 KB Output is correct
7 Incorrect 8 ms 6656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16888 KB Output is correct
2 Correct 72 ms 16888 KB Output is correct
3 Correct 49 ms 15224 KB Output is correct
4 Correct 16 ms 8192 KB Output is correct
5 Correct 14 ms 7552 KB Output is correct
6 Correct 21 ms 8960 KB Output is correct
7 Incorrect 8 ms 6656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10768 KB Output is correct
2 Correct 33 ms 10892 KB Output is correct
3 Correct 32 ms 10768 KB Output is correct
4 Correct 43 ms 10876 KB Output is correct
5 Correct 34 ms 10768 KB Output is correct
6 Correct 44 ms 10996 KB Output is correct
7 Correct 35 ms 11008 KB Output is correct
8 Correct 35 ms 10768 KB Output is correct
9 Correct 31 ms 10648 KB Output is correct
10 Correct 35 ms 11004 KB Output is correct
11 Correct 8 ms 6656 KB Output is correct
12 Correct 13 ms 8184 KB Output is correct
13 Correct 13 ms 8312 KB Output is correct
14 Correct 14 ms 8184 KB Output is correct
15 Correct 14 ms 8184 KB Output is correct
16 Correct 15 ms 8184 KB Output is correct
17 Correct 13 ms 7800 KB Output is correct
18 Correct 14 ms 8312 KB Output is correct
19 Correct 13 ms 8184 KB Output is correct
20 Incorrect 8 ms 6656 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16888 KB Output is correct
2 Correct 72 ms 16888 KB Output is correct
3 Correct 49 ms 15224 KB Output is correct
4 Correct 16 ms 8192 KB Output is correct
5 Correct 14 ms 7552 KB Output is correct
6 Correct 21 ms 8960 KB Output is correct
7 Incorrect 8 ms 6656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16888 KB Output is correct
2 Correct 72 ms 16888 KB Output is correct
3 Correct 49 ms 15224 KB Output is correct
4 Correct 16 ms 8192 KB Output is correct
5 Correct 14 ms 7552 KB Output is correct
6 Correct 21 ms 8960 KB Output is correct
7 Incorrect 8 ms 6656 KB Output isn't correct
8 Halted 0 ms 0 KB -