oj.uz

Submission #963600

# Submission time Handle Problem Language Result Execution time Memory
963600 2024-04-15T11:31:21 Z Amr Crocodile's Underground City (IOI11_crocodile) C++17
89 / 100
 692 ms 99124 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});
        //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;
        if(vis[cur]==0)
        {
            vis[cur] = 1;
            s.erase(s.begin());
            continue;
        }
        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].S)
            {
                s.erase({d[newn].S,newn});
                d[newn].S = w+dis;
                s.insert({d[newn].S,newn});
                if(d[newn].S<d[newn].F) swap(d[newn].F,d[newn].S);
            }
        }
    }
    return d[0].S;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:48: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]
   48 |         for(int i = 0; i < v[cur].sz; i++)
      |                          ^
crocodile.cpp:43:12: warning: unused variable 'dis1' [-Wunused-variable]
   43 |         ll dis1 = d[cur].F , dis2 = d[cur].S;
      |            ^~~~

Subtask #1
46.0 / 46.0

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

Subtask #2
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12932 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 4 ms 13188 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 5 ms 13400 KB Output is correct
13 Correct 5 ms 13400 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 4 ms 12892 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12888 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 4 ms 12932 KB Output is correct
8 Correct 3 ms 12888 KB Output is correct
9 Correct 4 ms 13188 KB Output is correct
10 Correct 2 ms 12892 KB Output is correct
11 Correct 3 ms 12892 KB Output is correct
12 Correct 5 ms 13400 KB Output is correct
13 Correct 5 ms 13400 KB Output is correct
14 Correct 3 ms 12892 KB Output is correct
15 Correct 4 ms 12892 KB Output is correct
16 Correct 429 ms 91244 KB Output is correct
17 Correct 64 ms 30692 KB Output is correct
18 Correct 112 ms 33104 KB Output is correct
19 Correct 692 ms 99124 KB Output is correct
20 Correct 243 ms 78824 KB Output is correct
21 Correct 36 ms 22632 KB Output is correct
22 Incorrect 270 ms 75632 KB Output isn't correct
23 Halted 0 ms 0 KB -