oj.uz

Submission #1046528

# Submission time Handle Problem Language Result Execution time Memory
1046528 2024-08-06T16:14:00 Z inesfi Crocodile's Underground City (IOI11_crocodile) C++14
100 / 100
 409 ms 48468 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;

//#define int long long

const int TAILLEMAXI=100*1000+2,INFINI=1000*1000*1000+2;
int noeud[TAILLEMAXI];
int fin[TAILLEMAXI];
int proches[TAILLEMAXI][2]; // numnoeud, premier ou deuxieme dist
vector<pair<int,int>> adja[TAILLEMAXI]; // noeud, dist
int d1,d2,ec,dist,num,chem;
set<pair<int,int>> encours;

int travel_plan(int nbnoeuds, int nbchemins, int chemins[][2], int L[], int nbsorties, int sorties[]){
    for (int i=0;i<nbchemins;i++){
        adja[chemins[i][0]].push_back({chemins[i][1],L[i]});
        adja[chemins[i][1]].push_back({chemins[i][0],L[i]});
    }
    for (int i=0;i<nbsorties;i++){
        fin[sorties[i]]=1;
    }
    for (int ipers=0;ipers<nbnoeuds;ipers++){
        if (fin[ipers]==0){
            d1=INFINI;
            d2=INFINI;
            for (int i=0;i<(int)adja[ipers].size();i++){
                if (fin[adja[ipers][i].first]==1){
                    if (adja[ipers][i].second<d1){
                        d2=d1;
                        d1=adja[ipers][i].second;
                    }
                    else if (adja[ipers][i].second<d2){
                        d2=adja[ipers][i].second;
                    }
                }
            }
            proches[ipers][0]=d1;
            proches[ipers][1]=d2;
            encours.insert({d2,ipers});
        }
    }
    while (encours.size()!=0){
        ec=(*(encours.begin())).second;
        dist=(*(encours.begin())).first;
        noeud[ec]=dist;
        encours.erase(encours.begin());
        fin[ec]=1;
        for (int i=0;i<(int)adja[ec].size();i++){
            if (fin[adja[ec][i].first]==0){
                num=adja[ec][i].first;
                chem=adja[ec][i].second;
                if (proches[num][0]>chem+dist){
                    encours.erase({proches[num][1],num});
                    encours.insert({proches[num][0],num});
                    proches[num][1]=proches[num][0];
                    proches[num][0]=chem+dist;
                }
                else if (proches[num][1]>chem+dist){
                    encours.erase({proches[num][1],num});
                    encours.insert({chem+dist,num});
                    proches[num][1]=chem+dist;
                }
            }
        }
    }
    return proches[0][1];
}

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 3 ms 9048 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 1 ms 6748 KB Output is correct
6 Correct 1 ms 6748 KB Output is correct
7 Correct 2 ms 7000 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 1 ms 6748 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 3 ms 9048 KB Output is correct
13 Correct 2 ms 9052 KB Output is correct
14 Correct 1 ms 6748 KB Output is correct
15 Correct 1 ms 6748 KB Output is correct
16 Correct 262 ms 44136 KB Output is correct
17 Correct 68 ms 20048 KB Output is correct
18 Correct 91 ms 20816 KB Output is correct
19 Correct 409 ms 48468 KB Output is correct
20 Correct 143 ms 41040 KB Output is correct
21 Correct 30 ms 14428 KB Output is correct
22 Correct 172 ms 38736 KB Output is correct