Submission #969462

#	Time	Username	Problem	Language	Result	Execution time	Memory
969462		Br3ad	Cyberland (APIO23_cyberland)	C++17	0 / 100	1617 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<bool> vis(N, false);

long double ans = 1e15;

void dfs(int cur, int prev, double time){
    if(power[cur] == 0 || cur == 0) ans = min(ans, time);

    vis[cur] = true;
    
    for(pair<int, int> p : adj[cur]){
        if(p.f == prev) continue;
        dfs(p.f, cur, 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();
    power.clear();
    // 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}
    dfs(h, -1, 0);
    return (vis[0])? ans : -1;
}

// int main(){
    
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
    
//     // ifstream cin();
//     // ofstream cout();
    
//     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