제출 #1361113

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361113		ibsha	경주 (Race) (IOI11_race)	C++20	9 / 100	3094 ms	14380 KiB

race

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
#define MOD 1000000007
#define endl '\n'
#define pb(v,i) (v).push_back(i)
#define vll vector<ll>
#define pll pair<ll,ll>

vector<pll> edges[200005];
ll edgedepth[200005], weightdepth[200005];
ll root, seconddaddy[200005];
int K;
vll visited;

void dfs(ll node, ll par){
    if (node == par) seconddaddy[node] = node;
    else if (par == root) seconddaddy[node] = node;
    else seconddaddy[node] = seconddaddy[par];

    if (weightdepth[node] > K) return;
    pb(visited, node);

    for (auto [nd, w] : edges[node]){
        if (nd == par) continue;
        edgedepth[nd] = edgedepth[node] + 1;
        weightdepth[nd] = weightdepth[node] + w;
        dfs(nd, node);
    }
}

int best_path(int N, int k, int H[][2], int L[]){
    K=k;
    int ans = 5*N;

    for (int i=0; i<N-1; i++){
        edges[H[i][0]].push_back({H[i][1], L[i]});
        edges[H[i][1]].push_back({H[i][0], L[i]});
    }

    for(root=0; root < N; root++){
        memset(edgedepth,0,sizeof(edgedepth));
        memset(weightdepth,0,sizeof(weightdepth));
        memset(seconddaddy,0,sizeof(seconddaddy));

        dfs(root, root);
        for (int ni=0; ni < visited.size(); ni++){
            for (int nj=ni+1; nj < visited.size(); nj++){
                ll i = visited[ni], j = visited[nj];
                if (seconddaddy[i] == seconddaddy[j] or weightdepth[i] + weightdepth[j] != K) continue;

                ans=min(ll(ans), edgedepth[i] + edgedepth[j]);
            }
        }
    }
    return (ans == 5*N ? -1 : ans);
}

• 서브태스크 1: 9 / 9
• 서브태스크 2: 0 / 12
• 서브태스크 3: 0 / 22
• 서브태스크 4: 0 / 57