Submission #426298

#	Time	Username	Problem	Language	Result	Execution time	Memory
426298		SAAD	Race (IOI11_race)	C++17	0 / 100	6 ms	5300 KiB

race

#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
//#include <bits/stdc++.h>
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
int n , k ;
bool visa[(int)3 * 100000];
vector <pair<int,int>> x[200002];
int best_path( int N, int K, int H[][2] ,int L[]) {
    n = N;k = K;
    for ( int i = 0 ; i < n-1 ; i++ ) {
        if (L[i])
        x[H[i][0]].pb( { L[i] , H[i][1] } );
        swap(H[i][0],H[i][1]);
        x[H[i][0]].pb( { L[i] , H[i][1] } );
    }
    int mn = (int)1e6;
    for ( int i = 0; i < n; i++ ) {
        memset(visa,0,sizeof(visa));
        priority_queue <pair<ll,int>> q ;
        q.push({0,i});
        int z = 1 , layer = 0 ;
        while ( !q.empty() ) {
            int a = q.top().S; ll cst = q.top().F;
            if ( layer > k ) break;
            q.pop();
            visa[a] = true ;
            cst *= -1 ;
            if(cst > k)continue; 
            if (cst == k) mn = min(mn,layer);
            for (auto j:x[a]) {
                if ( visa[j.S] || cst+j.F > k ) continue ;
                q.push( { -(cst+j.F) , j.S } );
            }
            z--;
            if ( !z ) {
                layer++;
                z = q.size();
            }
        }
    }
    return (mn==(int)1e6?-1:mn) ;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57