oj.uz

Submission #282030

# Submission time Handle Problem Language Result Execution time Memory
282030 2020-08-23T20:36:27 Z mat_v Crocodile's Underground City (IOI11_crocodile) C++14
0 / 100
 16 ms 23808 KB 
#include "crocodile.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
#define fb(i,a,b) for(int (i) = (a); (i) >= (b); --(i))
#define mod 998244353
#define xx first
#define yy second
#define all(a) (a).begin(), (a).end()
#define pb push_back
#define ll long long
#define pii pair<int,ll>


using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>,rb_tree_tag, tree_order_statistics_node_update> ordered_set;/// find_by_order(x)(x+1th) , order_of_key() (strictly less)
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());









int n,m;

vector<pii> graf[1000005];
pii dist[1000005];

priority_queue<pii> pq;

void djikstra(){
    while(!pq.empty()){
        pii sta = pq.top();
        ll duz = -sta.xx;
        int koji = sta.yy;
        cout << koji << " " << duz << "\n";
        cout << dist[koji].xx << " " << dist[koji].yy << "\n";
        pq.pop();
        for(auto c:graf[koji]){
            ll tmpduz = duz + c.yy;
            pii tr = dist[c.xx];
            pii novi = tr;
            if(tmpduz < novi.xx)novi = {tmpduz, novi.xx};
            else if(tmpduz < novi.yy)novi = {novi.xx, tmpduz};
            if(novi.yy < tr.yy){
                dist[c.xx] = novi;
                pq.push({-novi.yy, c.xx});
            }
            dist[c.xx] = novi;
        }
    }
}

int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
    n = N; m = M;
    ff(j,0,m - 1){
        int a = R[j][0];
        int b = R[j][1];
        a++; b++;
        ll c = L[j];
        graf[a].pb({b,c});
        graf[b].pb({a,c});
    }
    ll maks = 1e7;
    maks *= maks;
    ff(i,1,n)dist[i] = {maks, maks};
    ff(i,0,K - 1){
        int x = P[i];
        x++;
        pq.push({0,x});
        dist[x] = {0,0};
    }

    djikstra();

    return dist[1].yy;
}

Compilation message

crocodile.cpp: In function 'int travel_plan(int, int, int (*)[2], int*, int, int*)':
crocodile.cpp:7:27: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
crocodile.cpp:64:5: note: in expansion of macro 'ff'
   64 |     ff(j,0,m - 1){
      |     ^~
crocodile.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
crocodile.cpp:74:5: note: in expansion of macro 'ff'
   74 |     ff(i,1,n)dist[i] = {maks, maks};
      |     ^~
crocodile.cpp:7:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    7 | #define ff(i,a,b) for(int (i) = (a); (i) <= (b); ++(i))
      |                           ^
crocodile.cpp:75:5: note: in expansion of macro 'ff'
   75 |     ff(i,0,K - 1){
      |     ^~

Subtask #1
0 / 46.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -