제출 #933559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
933559		raul2008487	Dreaming (IOI13_dreaming)	C++17	100 / 100	50 ms	21364 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define ll int
#define in insert
#define pb push_back
#define vl vector<ll>
#define fi first
#define se second
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int sz = 2e5+5;
ll w, res;
vector<array<ll, 2>> adj[sz], dp(sz), leaf(sz);
bool used[sz];
ll node, R;
vl path;
void dfs1(ll v, ll p){
    //cout << v << endl;
    dp[v] = {0, 0};
    leaf[v] = {v, v};
    used[v] = 1; 
    for(array<ll, 2> e: adj[v]){
        if(!used[e[0]]){
            dfs1(e[0], v);
            if((dp[e[0]][0] + e[1]) > dp[v][0]){
                dp[v][1] = dp[v][0];
                leaf[v][1] = leaf[v][0];
                dp[v][0] = dp[e[0]][0] + e[1];
                leaf[v][0] = leaf[e[0]][0];
            }
            else if((dp[e[0]][0] + e[1]) > dp[v][1]){
                dp[v][1] = dp[e[0]][0] + e[1];
                leaf[v][1] = leaf[e[0]][0];
            }
        }
    }
    if((dp[v][0] + dp[v][1]) > res){
        node = v;
        res = dp[v][0] + dp[v][1];
    }
}
void getpath(ll v, ll p, ll target){
    for(array<ll, 2> e: adj[v]){
        if(e[0] != p){
            if(dp[e[0]][0] + e[1] == target){
                path.pb(e[1]);
                getpath(e[0], v, target - e[1]);
                return ;
            }
        }
    }
}
ll GetR(ll v){
    res = -1;
    dfs1(v, 0);
    //cout << endl << res << endl;
    ll l1 = leaf[node][0];
    ll l2 = leaf[node][1];
    ll bar = res / 2;
    path.clear();
    getpath(node, 0, dp[node][0]);
    reverse(all(path));
    getpath(node, 0, dp[node][1]);
    ll ret = res, cur = 0;
    R = max(R, res);
    for(auto x: path){
        cur += x;
        if(cur > bar){
            ret = min(ret, cur);
        }
        else{
            ret = min(ret, (res - cur));
        }
    }
    return ret;
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    ll n = N, m = M, i, j, k;
    w = L;
    for(i = 0; i < m; i++){
        adj[A[i] + 1].pb({B[i] + 1, T[i]});
        adj[B[i] + 1].pb({A[i] + 1, T[i]});
    }
    vl longest;
    for(i = 1; i <= n; i++){
        if(!used[i]){
            //cout << i << endl;
            longest.pb(GetR(i));
        }
    }
    sort(longest.rbegin(), longest.rend());
    if(longest.size() == 1){
        return R;
    }
    else if(longest.size() == 2){
        return max(R, longest[0] + longest[1] + w);
    }
    else{
        //cout << R << ' ' << longest[0] + longest[1] + w << ' ' << longest[1] + longest[2] + 2*w << endl; 
        return max({R, (longest[0] + longest[1] + w), (longest[1] + longest[2] + 2*w)});
    }
}
/*int main(){
    ll n = 12, m = 8, L = 2;
    ll a[8] = {0,8,2,5,5,1,1,10};
    ll b[8] = {8,2,7,11,1,3,9,6};
    ll t[8] = {4,2,4,3,7,1,5,3};
    cout <<  travelTime(n, m, L, a, b, t); 
}*/
/*

*/

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

dreaming.cpp: In function 'int GetR(int)':
dreaming.cpp:58:8: warning: unused variable 'l1' [-Wunused-variable]
   58 |     ll l1 = leaf[node][0];
      |        ^~
dreaming.cpp:59:8: warning: unused variable 'l2' [-Wunused-variable]
   59 |     ll l2 = leaf[node][1];
      |        ^~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:79:25: warning: unused variable 'j' [-Wunused-variable]
   79 |     ll n = N, m = M, i, j, k;
      |                         ^
dreaming.cpp:79:28: warning: unused variable 'k' [-Wunused-variable]
   79 |     ll n = N, m = M, i, j, k;
      |                            ^

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23