제출 #1305943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1305943		orgiloogii	악어의 지하 도시 (IOI11_crocodile)	C++20	46 / 100	1 ms	580 KiB

crocodile

#include "crocodile.h"
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
vector <vector <pair <int, int>>> adj;
vector <int> vis;
vector <long long> fin;
void init(int u, int w) {
    if (adj[u].size() == 1) {
        fin[u] = w;
    }
    vis[u] = 1;
    for (auto x : adj[u]) {
        if (vis[x.ff]) continue;
        init(x.ff, w + x.ss);
    }
}
void dfs(int u) {
    int m = INT_MAX, m1 = INT_MAX;
    vis[u] = 1;
    for (auto [x, y] : adj[u]) {
        if (vis[x]) continue;
        dfs(x);
        if (fin[x] < m) {
            m1 = m;
            m = fin[x];
        }
        else if (fin[x] < m1) {
            m1 = fin[x];
        }
    }
    if (adj[u].size() >= 3) {
        fin[u] = m1;
    }
}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
    adj.resize(n);
    vis.resize(n, 0);
    fin.resize(n, 0);
    for (int i = 0;i < m;i++) {
        adj[r[i][0]].push_back({r[i][1], l[i]});
        adj[r[i][1]].push_back({r[i][0], l[i]});
    }
    init(0, 0);
    vis.clear();
    vis.resize(n, 0);
    dfs(0);
    return fin[0];
}
//int main() {
//}

• Subtask 1: 46 / 46
• Subtask 2: 0 / 43
• Subtask 3: 0 / 11