Submission #969477

#	Time	Username	Problem	Language	Result	Execution time	Memory
969477		Br3ad	Cyberland (APIO23_cyberland)	C++17	0 / 100	1624 ms	2097152 KiB

cyberland

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)

const int N = 1e5 + 5;
const int M = 1e9 + 7; 
const int INF = 0x3f3f3f3f;

// Make variable global 
vector<vector<pair<int, int>>> adj(N, vector<pair<int, int>>());
vector<int> power(N);

vector<double> memo(N, -1);
long double ans = 1e15;
bool valid = false;

void dfsH(int cur, int prev, double time){
    if(power[cur] == 0){
        memo[cur] = time;
        return;
    }

    for(pair<int, int> p : adj[cur]){
        if(p.f == prev) continue;
        dfsH(p.f, cur, time + (double)p.s);
    }
}

void dfsStart(int cur, int prev, int h, double time){
    if(power[cur] == 0) {
        ans = min(ans, memo[cur]);
    }

    if(cur == h){
        valid = true;
        ans = min(ans, time);
        return;
    }

    for(pair<int, int> p : adj[cur]){
        if(p.f == prev) continue;
        dfsStart(p.f, cur, h, time + (double)p.s);
    }
}

double solve(int n, int m, int k, int h, vector<int> x, vector<int> y, vector<int> c, vector<int> arr){
    // Clear memory
    for(int i = 0; i < n; i++) adj[i].clear();
    for(int i = 0; i < n; i++) memo[i] = -1;
    power.clear();
    valid = false;
    // Make Adjacency List
    for(int i = 0; i < m; i++){
        adj[x[i]].PB(MP(y[i], c[i]));
        adj[y[i]].PB(MP(x[i], c[i]));
    }
    power = arr;
    // Solve Subtask 3
    // Connected tree, possible ability is arr{0, 1}
    dfsH(h, -1, 0);
    dfsStart(0, -1, h, 0);
    return (valid)? ans : -1;
}

// int main(){
    
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
    
//     // ifstream cin();
//     // ofstream cout();
    
//     // cout << solve(4, 3, 30, 3, {3, 2, 1}, {1, 1, 0}, {2, 3, 5}, {1, 1, 0, 1}) << endl;
//     // cout << solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1}) << endl;
//     // cout << solve(4, 4, 30, 3, {0, 0, 1, 2}, {1, 2, 3, 3}, {5, 4, 2, 4}, {1, 0, 2, 1}) << endl;
    
// }

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3