oj.uz

Submission #360971

# Submission time Handle Problem Language Result Execution time Memory
360971 2021-01-28T08:38:25 Z Yomapeed Dreaming (IOI13_dreaming) C++17
0 / 100
 58 ms 12524 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
#define pi 3.141592653589793238
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define MOD 1000000007
#define INF 999999999999999999 
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define mt make_tuple 
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
 
 
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
 
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int nax = 1e5 + 1;
vector<pair<int,int>> adj[nax];
bool visited[nax];
vector<int> maxpafs;
int maxdia;
int best, dist, dp[nax];
void dfs(int a, int par, int d){
    if(d >= dist){
        best = a;
        dist = d;
    }
    visited[a] = true;
    for(auto u : adj[a]){
        if(u.ff != par){
            dp[u.ff] = dp[a] + u.ss;
            dfs(u.ff, a, d + u.ss);
        }
    }
}
void dfs2(int a, int par, int d){
    if(d >= dist){
        dist = d;
    }
    for(auto u : adj[a]){
        if(u.ff != par){
            dfs2(u.ff, a, d + u.ss);
        }
    }
}
void dfs3(int a, int par, int d, int ans){
    for(auto u : adj[a]){
        if(u.ff != par){
            ans = min(ans, max(dp[u.ff], d));
            dfs3(u.ff, a, d + u.ss, ans);
        }
    }
}
void dfs4(int a, int par, int d, int ans, int deepest){
    for(auto u : adj[a]){
        if(u.ff != par){
            ans = min(ans, max(dp[u.ff], d + deepest));
            dfs4(u.ff, a, d + u.ss, ans, deepest);
        }
    }
}
void f(int id){
    int ans = INT_MAX;
    vector<pair<int,int>> nodes;
    for(auto u : adj[id]){
        nodes.pb({u.ff, u.ss});
    }
    if(nodes.size() == 0){
        maxpafs.pb(0);
        return;
    }
    dfs3(nodes[0].ff, id, nodes[0].ss, ans);
    auto u = nodes[0];
    int deepest = dp[u.ff] + u.ss;
    for(int i = 1; i < nodes.size(); i++){
        dfs4(nodes[i].ff, id, nodes[i].ss, ans, deepest);
        deepest = max(deepest, nodes[i].ss + dp[nodes[i].ff]);
    }
    maxpafs.pb(ans);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i = 0; i < M; i++){
        adj[A[i]].pb({B[i], T[i]});
        swap(A[i], B[i]);
        adj[A[i]].pb({B[i], T[i]});
    }
    for(int i = 0; i < N; i++){
        if(!visited[i]){
            dist = 0;
            dfs(i, -1, 0);
            dfs2(best, -1, 0);
            maxdia = max(maxdia, dist);
            f(i);
        }
    }
    int ans = maxdia;
    if(maxpafs.size() == 1){
        return maxdia;
    }
    if(maxpafs.size() == 2){
        ans = max(ans, maxpafs[0] + L + maxpafs[1]);
        return ans;
    }
    int sz = maxpafs.size();
    int  x = sz - 1, y = sz - 2;
    sort(maxpafs.begin(), maxpafs.end());
    for(int i = 0; i < sz; i++){
        ans = min(ans, max({maxdia, maxpafs[i] + L + maxpafs[x], maxpafs[y] + maxpafs[x] + 2 * L}));
        if(y == i){
            y--;
        }
        if(x == i){
            x--;
        }
    }
    return ans;
} 
// int main() {
//     //freopen("input.txt", "r", stdin);
//     //freopen("output.txt", "w", stdout);
//     fast;
//     ll T = 1, i, j;
    
//     //cin >> T;
//     while (T--) {
//         int A[] = {0,8,2,5,5,1,1,10};
//         int B[] = {8,2,7,11,1,3,9,6};
//         int C[] = {4,2,4,3,7,1,5,3};
//         int N = 12, L = 2, M = 8;
    
//     }
//     return 0;
// }

Compilation message

dreaming.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
dreaming.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
dreaming.cpp: In function 'void f(int)':
dreaming.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 1; i < nodes.size(); i++){
      |                    ~~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12524 KB Output is correct
2 Correct 58 ms 12524 KB Output is correct
3 Correct 37 ms 10476 KB Output is correct
4 Correct 9 ms 4204 KB Output is correct
5 Correct 7 ms 3564 KB Output is correct
6 Correct 14 ms 4844 KB Output is correct
7 Incorrect 2 ms 2668 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Incorrect 3 ms 2668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12524 KB Output is correct
2 Correct 58 ms 12524 KB Output is correct
3 Correct 37 ms 10476 KB Output is correct
4 Correct 9 ms 4204 KB Output is correct
5 Correct 7 ms 3564 KB Output is correct
6 Correct 14 ms 4844 KB Output is correct
7 Incorrect 2 ms 2668 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 2 ms 2668 KB Output is correct
3 Incorrect 3 ms 2668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 12524 KB Output is correct
2 Correct 58 ms 12524 KB Output is correct
3 Correct 37 ms 10476 KB Output is correct
4 Correct 9 ms 4204 KB Output is correct
5 Correct 7 ms 3564 KB Output is correct
6 Correct 14 ms 4844 KB Output is correct
7 Incorrect 2 ms 2668 KB Output isn't correct
8 Halted 0 ms 0 KB -