oj.uz

Submission #1070213

# Submission time Handle Problem Language Result Execution time Memory
1070213 2024-08-22T12:17:54 Z TsotneSV Race (IOI11_race) C++17
9 / 100
 91 ms 41556 KB 
#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#include "race.h"
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/
//#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") // codeforces

// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;


const int inf=1e9,MAXN=2e5+5; 

vpi g[MAXN]; set<pair<ll,int>> st[MAXN];
int ans;

void dfs(int v,int p,int d,int k,ll curr = 0) {

    for(auto [u,w] : g[v]) {

        if(u == p) continue;

        dfs(u,v,d+1,k,curr+w);

        if(st[v].size() < st[u].size()) swap(st[u],st[v]);

        for(auto x : st[u]) {
            auto y = st[v].lower_bound({x.fi,0});
            if(y != st[v].end() and (*y).fi == k - x.fi) ans = min(ans,(*y).se + x.se - 2 * d);
        }

        for(auto x : st[u]) st[v].ins(x);
    }


    auto x = st[v].lower_bound({curr+k,0});

    if(x != st[v].end() and (*x).fi == curr+k) ans = min(ans,(*x).se - d);

    st[v].ins({curr,d});
}

int best_path(int N, int K, int H[][2], int L[]) {

    ans = inf; 

    for(int i=0;i<N;i++) g[i].clear(),st[i].clear();

    for(int i=0;i<N-1;i++) {
        g[H[i][0]].pb({H[i][1],L[i]});
        g[H[i][1]].pb({H[i][0],L[i]});
    }

    dfs(0,-1,0,K);
    
    return (ans == inf ? -1 : ans);

}

/* int main() {

    send help

    int H[][2] = { {0,1}, {0,2}, {2,3}, {3,4}, {4,5}, {0,6}, {6,7}, {6,8}, {8,9}, {8,10} };
    int L[] = {3,4,5,4,6,3,2,5,6,7};

    printl(best_path(11,12,H,L));

    return 0;

} */

Compilation message

race.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      |

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 3 ms 18012 KB Output is correct
5 Correct 3 ms 18012 KB Output is correct
6 Correct 4 ms 18012 KB Output is correct
7 Correct 3 ms 18012 KB Output is correct
8 Correct 3 ms 18012 KB Output is correct
9 Correct 3 ms 18100 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 3 ms 18012 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 3 ms 18012 KB Output is correct
17 Correct 3 ms 18148 KB Output is correct
18 Correct 3 ms 18012 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 3 ms 18012 KB Output is correct
5 Correct 3 ms 18012 KB Output is correct
6 Correct 4 ms 18012 KB Output is correct
7 Correct 3 ms 18012 KB Output is correct
8 Correct 3 ms 18012 KB Output is correct
9 Correct 3 ms 18100 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 3 ms 18012 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 3 ms 18012 KB Output is correct
17 Correct 3 ms 18148 KB Output is correct
18 Correct 3 ms 18012 KB Output is correct
19 Incorrect 3 ms 18172 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 3 ms 18012 KB Output is correct
5 Correct 3 ms 18012 KB Output is correct
6 Correct 4 ms 18012 KB Output is correct
7 Correct 3 ms 18012 KB Output is correct
8 Correct 3 ms 18012 KB Output is correct
9 Correct 3 ms 18100 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 3 ms 18012 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 3 ms 18012 KB Output is correct
17 Correct 3 ms 18148 KB Output is correct
18 Correct 3 ms 18012 KB Output is correct
19 Incorrect 91 ms 41556 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 18012 KB Output is correct
2 Correct 3 ms 18012 KB Output is correct
3 Correct 3 ms 18012 KB Output is correct
4 Correct 3 ms 18012 KB Output is correct
5 Correct 3 ms 18012 KB Output is correct
6 Correct 4 ms 18012 KB Output is correct
7 Correct 3 ms 18012 KB Output is correct
8 Correct 3 ms 18012 KB Output is correct
9 Correct 3 ms 18100 KB Output is correct
10 Correct 3 ms 18012 KB Output is correct
11 Correct 3 ms 18012 KB Output is correct
12 Correct 3 ms 18012 KB Output is correct
13 Correct 3 ms 18012 KB Output is correct
14 Correct 3 ms 18012 KB Output is correct
15 Correct 3 ms 18012 KB Output is correct
16 Correct 3 ms 18012 KB Output is correct
17 Correct 3 ms 18148 KB Output is correct
18 Correct 3 ms 18012 KB Output is correct
19 Incorrect 3 ms 18172 KB Output isn't correct
20 Halted 0 ms 0 KB -