oj.uz

Submission #963622

# Submission time Handle Problem Language Result Execution time Memory
963622 2024-04-15T11:53:01 Z Amr Crocodile's Underground City (IOI11_crocodile) C++17
100 / 100
 662 ms 96112 KB 
#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz size()
const int N = 3e5+2;
const ll inf = 1e18;
ll vis[N];
pair<ll,ll> d[N];
vector<pair<ll,ll> > v[N];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    for(int i = 0; i < M; i++)
    {
        ll x = R[i][0] , y = R[i][1];
        ll z = L[i];
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
    for(int i = 0; i < N; i++) d[i].F = d[i].S = inf;
    multiset<pair<ll,ll> > s;
    for(int i = 0; i < K; i++)
    {
        ll x = P[i];
        s.insert({0,x});
        //s.insert({0,x});
        //vis[x] = 1;
        d[x] = {0,0};
    }
    while(s.sz)
    {
        ll cur = s.begin()->S;

        //cout << cur << " " << s.begin()->F << endl;
        ll dis1 = d[cur].F , dis2 = d[cur].S;
        s.erase(s.begin());
        ll dis = dis2;
        //vis[cur]++;
        //if(vis[i]==1) continue;
        for(int i = 0; i < v[cur].sz; i++)
        {
            ll newn = v[cur][i].F , w = v[cur][i].S;

            //if(vis[newn]==2) continue;
            if(w+dis<d[newn].F)
                {
                    if(d[newn].F!=inf)
                    {
                        if(d[newn].S!=inf)
                        s.erase({d[newn].S,newn});
                        d[newn].S = d[newn].F;
                        s.insert({d[newn].S,newn});
                    }
                    d[newn].F=w+dis; continue;
                }
            if(w+dis<d[newn].S)
            {
                if(d[newn].S!=inf)
                s.erase({d[newn].S,newn});
                d[newn].S = w+dis;
                s.insert({d[newn].S,newn});

            }
        }
    }
    return d[0].S;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 0; i < v[cur].sz; i++)
      |                          ^
crocodile.cpp:37:12: warning: unused variable 'dis1' [-Wunused-variable]
   37 |         ll dis1 = d[cur].F , dis2 = d[cur].S;
      |            ^~~~

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12924 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 13048 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12900 KB Output is correct
8 Correct 3 ms 12896 KB Output is correct

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12924 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 13048 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12900 KB Output is correct
8 Correct 3 ms 12896 KB Output is correct
9 Correct 4 ms 13148 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 4 ms 12888 KB Output is correct
12 Correct 6 ms 13448 KB Output is correct
13 Correct 5 ms 13408 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12952 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12924 KB Output is correct
2 Correct 3 ms 12888 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 3 ms 13048 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12900 KB Output is correct
8 Correct 3 ms 12896 KB Output is correct
9 Correct 4 ms 13148 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 4 ms 12888 KB Output is correct
12 Correct 6 ms 13448 KB Output is correct
13 Correct 5 ms 13408 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 3 ms 12952 KB Output is correct
16 Correct 448 ms 90840 KB Output is correct
17 Correct 59 ms 29968 KB Output is correct
18 Correct 80 ms 32228 KB Output is correct
19 Correct 662 ms 96112 KB Output is correct
20 Correct 262 ms 78816 KB Output is correct
21 Correct 45 ms 22356 KB Output is correct
22 Correct 280 ms 75484 KB Output is correct