oj.uz

Submission #800204

# Submission time Handle Problem Language Result Execution time Memory
800204 2023-08-01T11:51:34 Z Boomyday Crocodile's Underground City (IOI11_crocodile) C++17
46 / 100
 2 ms 724 KB 

//
// Created by adavy on 3/3/2023.
//
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using db = double;
using str = string;

using ii = pair<int,int>;
using pl = pair<ll,ll>;
using pd = pair<db,db>;

using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vii = vector<ii>;
using vpl = vector<pl>;
using vpd = vector<pd>;

#define tcT template<class T
#define tcTU tcT, class U

tcT> using V = vector<T>;
tcT, size_t SZ> using AR = array<T,SZ>;
tcT> using PR = pair<T,T>;

// pairs
#define mp make_pair
#define f first
#define s second

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)


#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define eb emplace_back
#define pf push_front

const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5;
const ll INF = 1e18; // not too close to LLONG_MAX
const ld PI = acos((ld)-1);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1}; // for every grid problem!!


#include "crocodile.h"
/*
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 50000
#define MAX_M 10000000

static int N, M;
static int R[MAX_M][2];
static int L[MAX_M];
static int K;
static int P[MAX_N];
static int solution;

inline
void my_assert(int e) {if (!e) abort();}

void read_input()
{
    int i;
    my_assert(3==scanf("%d %d %d",&N,&M,&K));
    for(i=0; i<M; i++)
        my_assert(3==scanf("%d %d %d",&R[i][0],&R[i][1],&L[i]));
    for(i=0; i<K; i++)
        my_assert(1==scanf("%d",&P[i]));
    my_assert(1==scanf("%d",&solution));
}
*/
vl dist;
vb vis;
vi par;
vector<vector<pair<ll,int>>> adj;

void dfs(int nd){
    vis[nd] = 1;
    if (adj[nd].size() == 1){
         dist[nd] = 0;
         par[nd] = adj[nd][0].s;
         return;
    }

    trav(nei, adj[nd]){ if (!vis[nei.s]) dfs(nei.s); else par[nd] = nei.s;}
    ll bst = INF, sbst = INF;
    for(auto&[len, nei]:adj[nd]){
        if (nei == par[nd]) continue;
        ll distN = dist[nei] + len;
        if (distN < bst) {
            sbst = bst; bst = distN;
        }
        else if (distN < sbst) {
            sbst = distN;
        }
    }
    dist[nd] = sbst;


}

int travel_plan(int n, int m, int r[][2], int l[], int k, int p[])
{
    adj.rsz(n);
    vis.rsz(n);
    dist.rsz(n);
    par.rsz(n);
    fill(all(vis),0);
    fill(all(dist),INF);
    F0R(i, k){
        dist[p[i]] = 0;
    }


    F0R(i, m){
        adj[r[i][0]].pb({l[i], r[i][1]});
        adj[r[i][1]].pb({l[i], r[i][0]});
    }

    dfs(0);
    
    return dist[0];




}

/*
int main()javascript:tab_clicked(1)
{
    int ans;
    read_input();
    ans = travel_plan(N,M,R,L,K,P);
    if(ans==solution)
        printf("Correct.\n");
    else
        printf("Incorrect. Returned %d, Expected %d.\n",ans,solution);

    return 0;
}




*/

Subtask #1
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 452 KB Output is correct

Subtask #2
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Incorrect 2 ms 724 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 452 KB Output is correct
9 Incorrect 2 ms 724 KB Output isn't correct
10 Halted 0 ms 0 KB -