oj.uz

Submission #969487

# Submission time Handle Problem Language Result Execution time Memory
969487 2024-04-25T08:33:43 Z Br3ad Cyberland (APIO23_cyberland) C++17
21 / 100
 1518 ms 2097152 KB 
#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;

    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;
    ans = 1e15;
    // 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1518 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4944 KB Correct.
2 Correct 18 ms 4956 KB Correct.
3 Correct 18 ms 4992 KB Correct.
4 Correct 19 ms 4956 KB Correct.
5 Correct 18 ms 4956 KB Correct.
6 Correct 18 ms 5532 KB Correct.
7 Correct 26 ms 5728 KB Correct.
8 Correct 14 ms 5728 KB Correct.
9 Correct 19 ms 4928 KB Correct.
10 Correct 18 ms 4948 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5076 KB Correct.
2 Correct 19 ms 5028 KB Correct.
3 Correct 18 ms 5172 KB Correct.
4 Correct 22 ms 4808 KB Correct.
5 Correct 22 ms 4912 KB Correct.
6 Correct 5 ms 4700 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 11528 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1169 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1187 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1180 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 1170 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -