oj.uz

Submission #231479

# Submission time Handle Problem Language Result Execution time Memory
231479 2020-05-13T17:57:08 Z nickmet2004 Dreaming (IOI13_dreaming) C++11
0 / 100
 63 ms 15352 KB 
#include<bits/stdc++.h>
#include"dreaming.h"
#define f first
#define s second
#define ll long long
using namespace std;

const int N = 2e5 + 500;
typedef pair<int , int> ipair;

int n , m , L;
vector<ipair> adj[N];
int component[N];
int dpD[N] , dpU[N];
bool vis[N];
int cmp;
int MN[N] , mx1[N] , mx2[N];
vector<int> dist;

void dfsD(int u , int BOSS){
    vis[u] = 1;
    component[u] = cmp;
    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(u == BOSS){
            if(mx2[component[v]] < dpD[v] + w) mx2[component[v]] = dpD[v] + w;
            if(mx2[component[v]] > mx1[component[v]]) swap(mx2[component[v]] , mx1[component[v]]);
        }
    }
}
void dfsU(int u , int BOSS){
    vis[u] = 1;
    for(ipair x : adj[u]){
        int v = x.f , w = x.s;
        if(vis[v]) continue;
        if(u == BOSS){
            if(dpD[v] + w == mx1[component[v]]){
                if(mx2[component[v]] == -1){
                    dpU[v] = w;
                } else
                dpU[v] = mx2[component[v]] + w;
            } else {
                dpU[v] = mx1[component[v]] + w;
            }
        } else
            dpU[v] = dpU[u] + w;

        dfsU(v , BOSS);
    }
}

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]);
    }
    for(int i = 0; i < n; ++i){
        mx1[cmp] = -1 , mx2[cmp] = -1;
        if(!vis[i]) {dfsD(i , i);  cmp++;};
    }

    for(int i = 0; i < n; ++i) vis[i] = 0;
    for(int i = 0; i < n; ++i){
        if(!vis[i]) dfsU(i , i);
    }

    /*
    for(int i = 0; i < n; ++i){
        cerr << i << " i : " << dpD[i] << " dpD " << " : " << " dpU " << dpU[i] << endl;
    }
    */
    ///cerr << cmp - 1<< " CMP " << endl;
    for(int i = 0; i < cmp; ++i) MN[i] = 2e9;
    for(int i = 0; i < n; ++i){
        MN[component[i]] = min(MN[component[i]] , max(dpD[i] , dpU[i]));
    }
    //for(int i = 0; i < cmp; ++i) cout << i << " cmp " << MN[i] << endl;
    for(int i = 0; i < cmp; ++i){
        dist.emplace_back(MN[i]);
    } sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
    return max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);

}
/*
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);
    }
    for(int i = 0; i < n; ++i){
        mx1[cmp] = -1 , mx2[cmp] = -1;
        if(!vis[i]) {dfsD(i , i);  cmp++;};
    }

    for(int i = 0; i < n; ++i) vis[i] = 0;
    for(int i = 0; i < n; ++i){
        if(!vis[i]) dfsU(i , i);
    }


    for(int i = 0; i < n; ++i){
        cerr << i << " i : " << dpD[i] << " dpD " << " : " << " dpU " << dpU[i] << endl;
    }

    ///cerr << cmp - 1<< " CMP " << endl;
    for(int i = 0; i < cmp; ++i) MN[i] = 1e18;
    for(int i = 0; i < n; ++i){
        MN[component[i]] = min(MN[component[i]] , max(dpD[i] , dpU[i]));
    }
    //for(int i = 0; i < cmp; ++i) cout << i << " cmp " << MN[i] << endl;
    for(int i = 0; i < cmp; ++i){
        dist.emplace_back(MN[i]);
    } sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
    cout << max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L) << endl;

return 0;
}
*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 15352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 15352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 15352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10104 KB Output is correct
2 Correct 32 ms 10112 KB Output is correct
3 Correct 33 ms 10112 KB Output is correct
4 Correct 34 ms 9976 KB Output is correct
5 Correct 35 ms 10104 KB Output is correct
6 Correct 35 ms 10616 KB Output is correct
7 Correct 34 ms 10488 KB Output is correct
8 Correct 32 ms 9976 KB Output is correct
9 Correct 31 ms 9984 KB Output is correct
10 Correct 33 ms 10240 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 12 ms 8060 KB Output is correct
13 Correct 12 ms 8188 KB Output is correct
14 Correct 12 ms 8060 KB Output is correct
15 Correct 12 ms 8060 KB Output is correct
16 Correct 12 ms 8060 KB Output is correct
17 Correct 12 ms 7676 KB Output is correct
18 Correct 12 ms 8228 KB Output is correct
19 Correct 12 ms 8020 KB Output is correct
20 Incorrect 7 ms 5120 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 15352 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 15352 KB Output isn't correct
2 Halted 0 ms 0 KB -