제출 #704090

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704090		Alihan_8	꿈 (IOI13_dreaming)	C++17	100 / 100	103 ms	16488 KiB

dreaming

#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, itr);
    }
}
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

컴파일 시 표준 에러 (stderr) 메시지

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: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23