oj.uz

Submission #1016191

# Submission time Handle Problem Language Result Execution time Memory
1016191 2024-07-07T13:34:33 Z inesfi Cyberland (APIO23_cyberland) C++17
44 / 100
 3000 ms 23336 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 3037 ms 16344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 16216 KB Correct.
2 Correct 48 ms 17196 KB Correct.
3 Correct 44 ms 17244 KB Correct.
4 Correct 46 ms 17232 KB Correct.
5 Correct 47 ms 17232 KB Correct.
6 Correct 16 ms 17500 KB Correct.
7 Correct 20 ms 17964 KB Correct.
8 Correct 10 ms 17928 KB Correct.
9 Correct 319 ms 17008 KB Correct.
10 Correct 300 ms 16976 KB Correct.

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 16204 KB Correct.
2 Correct 45 ms 16980 KB Correct.
3 Correct 48 ms 16984 KB Correct.
4 Correct 288 ms 16980 KB Correct.
5 Correct 326 ms 16992 KB Correct.
6 Correct 5 ms 16764 KB Correct.

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 20484 KB Correct.
2 Incorrect 51 ms 16252 KB Wrong Answer.
3 Halted 0 ms 0 KB -

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 16240 KB Correct.
2 Correct 55 ms 17360 KB Correct.
3 Correct 50 ms 17236 KB Correct.
4 Correct 23 ms 18268 KB Correct.
5 Correct 340 ms 16892 KB Correct.

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 16216 KB Correct.
2 Correct 46 ms 16980 KB Correct.
3 Correct 29 ms 23336 KB Correct.
4 Correct 15 ms 17440 KB Correct.
5 Correct 316 ms 16980 KB Correct.
6 Correct 46 ms 17236 KB Correct.

Subtask #7
0.0 / 29.0

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

Subtask #8
0.0 / 3.0

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