oj.uz

Submission #1016217

# Submission time Handle Problem Language Result Execution time Memory
1016217 2024-07-07T14:02:35 Z inesfi Cyberland (APIO23_cyberland) C++17
44 / 100
 3000 ms 21332 KB 
#include "cyberland.h"
#include<bits/stdc++.h>
using namespace std;

const int TAILLEMAXI=100*1000+2,DIVMAXI=32;
int dejavu[TAILLEMAXI];
int deja[TAILLEMAXI][DIVMAXI];
vector<int> pv;
int zero[TAILLEMAXI];
vector<pair<int,int>> adja[TAILLEMAXI];
set<tuple<double,int,int>> encours;
set<tuple<double,int,int>>::iterator it;
int pos,nbdiv2,arrive;
double dist;

void dfs(int n){
    if (n==arrive){
        dejavu[n]=1;
        return ;
    }
    if (dejavu[n]==1){
        return ;
    }
    if (pv[n]==0){
        zero[n]=1;
    }
    dejavu[n]=1;
    for (int i=0;i<(int)adja[n].size();i++){
        dfs(adja[n][i].first);
    }
}

double solve(int nbnoeuds, int nbarretes, int K, int H,vector<int> deb,vector<int> fin,vector<int> temps,vector<int> arr) {
    for (int i=0;i<TAILLEMAXI;i++){
        adja[i].clear();
        zero[i]=0;
        dejavu[i]=0;
    }
    encours.clear();
    pv.clear();
    pv=arr;
    arrive=H;
    K=min(K,DIVMAXI-1);
    for (int i=0;i<nbarretes;i++){
        adja[deb[i]].push_back(make_pair(fin[i],temps[i]));
        adja[fin[i]].push_back(make_pair(deb[i],temps[i]));
    }
    dfs(0);
    zero[0]=1;
    encours.insert(make_tuple(0,arrive,0));
    for (int i=0;i<TAILLEMAXI;i++){
        for (int j=0;j<DIVMAXI;j++){
            deja[i][j]=-1;
        }
    }
    while (encours.size()!=0){
        it=encours.begin();
        dist=get<0>(*(it));
        pos=get<1>(*(it));
        nbdiv2=get<2>(*(it));
        encours.erase(it);
        if (deja[pos][nbdiv2]==-1){
            if (zero[pos]==1){
                return dist;
            }
            deja[pos][nbdiv2]=dist;
            if (arr[pos]==2 and nbdiv2<K){
                for (int ivois=0;ivois<(int)adja[pos].size();ivois++){
                    if (deja[adja[pos][ivois].first][nbdiv2+1]==-1){
                        encours.insert(make_tuple(dist+(double)adja[pos][ivois].second*(double)pow(0.5,(nbdiv2+1)),adja[pos][ivois].first,nbdiv2+1));
                    }
                    if (deja[adja[pos][ivois].first][nbdiv2]==-1){
                        encours.insert(make_tuple(dist+(double)adja[pos][ivois].second*(double)pow(0.5,(nbdiv2)),adja[pos][ivois].first,nbdiv2));
                    }
                }
            }
            else {
                for (int ivois=0;ivois<(int)adja[pos].size();ivois++){
                    if (deja[adja[pos][ivois].first][nbdiv2]==-1){
                        encours.insert(make_tuple(dist+(double)adja[pos][ivois].second*(double)pow(0.5,(nbdiv2)),adja[pos][ivois].first,nbdiv2));
                    }
                }
            }
        }
    }
    return -1;
}

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3067 ms 16212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 16176 KB Correct.
2 Correct 43 ms 16212 KB Correct.
3 Correct 52 ms 16212 KB Correct.
4 Correct 42 ms 16220 KB Correct.
5 Correct 50 ms 16252 KB Correct.
6 Correct 15 ms 16728 KB Correct.
7 Correct 18 ms 16732 KB Correct.
8 Correct 9 ms 17308 KB Correct.
9 Correct 285 ms 16140 KB Correct.
10 Correct 321 ms 16400 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 16184 KB Correct.
2 Correct 49 ms 16192 KB Correct.
3 Correct 38 ms 16220 KB Correct.
4 Correct 294 ms 15964 KB Correct.
5 Correct 282 ms 16140 KB Correct.
6 Correct 5 ms 16476 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 20488 KB Correct.
2 Incorrect 41 ms 16224 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16320 KB Correct.
2 Correct 50 ms 16220 KB Correct.
3 Correct 46 ms 16472 KB Correct.
4 Correct 23 ms 17244 KB Correct.
5 Correct 305 ms 16108 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16216 KB Correct.
2 Correct 40 ms 16216 KB Correct.
3 Correct 27 ms 21332 KB Correct.
4 Correct 15 ms 16732 KB Correct.
5 Correct 302 ms 16132 KB Correct.
6 Correct 44 ms 16220 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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