oj.uz

답안 #985395

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
985395 2024-05-17T17:54:08 Z kkkkkkkk 사이버랜드 (APIO23_cyberland) C++17
0 / 100
 3000 ms 30044 KB 
#include <bits/stdc++.h>

using namespace std;

bool vis[100005];
vector<pair<int,int> > G[100005];
vector<int> arr1;

bool ima_pat(int teme, int kraj) {
    if (teme==kraj) 
        return true;
    vis[teme]=1;
    bool ok=false;
    for (auto next:G[teme]) 
        if (!vis[next.first])
            ok=(ok|ima_pat(next.first,kraj));
    return ok;
}

double rez=1e18, dp[100005][35];

void f(int teme, int kraj, double vreme, int k) {
    if (dp[teme][k]<=vreme)
        return;
    dp[teme][k]=vreme;
    for (auto next:G[teme]) {
        if (k>0&&arr1[next.first]==0) 
            f(next.first, kraj, 0, k-1);
        else if (k>0&&arr1[next.first]==2) 
            f(next.first, kraj, vreme/2.0, k-1);
        f(next.first, kraj, vreme+next.second, k);
    }
}

double solve(int n, int m, int k, int h, vector<int> a, vector<int> b, vector<int> c, vector<int> arr) {
    for (int i=0;i<m;i++) {
        G[a[i]].push_back({b[i],c[i]});
        G[b[i]].push_back({a[i],c[i]});
    }
    arr1=arr;
    for (int i=0;i<n;i++)
        vis[i]=0;
    for (int i=0;i<n;i++)
        for (int j=0;j<35;j++)
            dp[i][j]=1e18;
    if (!ima_pat(0,h)) return -1;
    f(0, h, 0, k);
    double r=1e18;
    for (int i=0;i<35;i++)
        r=min(r,dp[h][i]);
    return r;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3072 ms 3352 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3063 ms 6324 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3038 ms 5708 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3063 ms 30044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3058 ms 6068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3038 ms 5716 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3027 ms 5916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3035 ms 5744 KB Time limit exceeded
2 Halted 0 ms 0 KB -