oj.uz

Submission #704086

# Submission time Handle Problem Language Result Execution time Memory
704086 2023-03-01T14:19:25 Z Alihan_8 Dreaming (IOI13_dreaming) C++17
0 / 100
 42 ms 21796 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
// include <ext/pb_ds/assoc_container.hpp>
// include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
// define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
#define mpr make_pair
#define ln '\n'
void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
//#define int long long
const int N = 1e5+1;
vector <pair<int,int>> g[N];
int used[N], Mx, it, diameter;
array <int,2> dis[N];
vector <int> V;
void dfs(int x, int par, int depth, int itr){
    if ( itr == -1 ) V.pb(x);
    else dis[x][itr] = depth;
    if ( depth > Mx ){
        Mx = depth, it = x;
    }
    for ( auto [to, len]: g[x] ){
        if ( to == par ) continue;
        dfs(to, x, depth+len, it);
    }
}
int best(int root){
    dfs(root, root, 0, -1); Mx = 0;
    dfs(it, it, 0, 0); Mx = 0;
    dfs(it, it, 0, 1); 
    diameter = max(diameter, Mx);
    Mx = 0;
    int Mn = 1e9;
    for ( auto i: V ){
        used[i] = true;
        Mn = min(Mn, max(dis[i][0], dis[i][1]));
    }
    V.clear();
    return Mn;
}
int travelTime(int n, int M, int L, int A[], int B[], int T[]) {
    for ( int i = 0; i < M; i++ ){
        g[A[i]].pb({B[i], T[i]});
        g[B[i]].pb({A[i], T[i]});
    }
    vector <int> res;
    for ( int i = 0; i < n; i++ ){
        if ( used[i] ) continue;
        res.pb(best(i));
    }
    sort(all(res), greater <int> ());
    int Mx = diameter;
    if ( (int)res.size() > 1 ) Mx = max(Mx, res[0]+res[1]+L);
    if ( (int)res.size() > 2 ){
        Mx = max(Mx, res[1]+res[2]+L*2);
    }
    return Mx;
}
#if false
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, M, L; cin >> n >> M >> L;
    int A[M], B[M], T[M];
    for ( int i = 0; i < M; i++ ){
        cin >> A[i] >> B[i] >> T[i];
    }
    cout << travelTime(n, M, L, A, B, T);

    cout << '\n';
/*
 12 8 2
 0 8 4
 8 2 2
 2 7 4
 5 11 3
 5 1 7
 1 3 1
 1 9 5
 10 6 3
*/
}
#endif

Compilation message

dreaming.cpp: In function 'void IO(std::string)':
dreaming.cpp:12:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:12:70: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | void IO(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 21796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 21796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 6616 KB Output is correct
2 Correct 23 ms 7160 KB Output is correct
3 Incorrect 25 ms 7116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 42 ms 21796 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -