oj.uz

Submission #898812

# Submission time Handle Problem Language Result Execution time Memory
898812 2024-01-05T06:54:30 Z Sir_Ahmed_Imran Race (IOI11_race) C++17
9 / 100
 67 ms 26828 KB 
                              ///~~~LOTA~~~///
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define MAXN 200000
int o;
int pwr[18];
int siz[MAXN];
int mark[MAXN];
int dept[MAXN];
int par[MAXN][18];
vector<pii> a[MAXN];
void dfs(int v,int u){
    par[v][0]=u;
    for(auto& i:a[v]){
        if(i.ff==u) continue;
        dept[i.ff]=dept[v]+i.ss;
        dfs(i.ff,v);
    }
}
int best_path(int n,int x,int e[MAXN][2],int l[MAXN]){
    o=n;
    int p,q,r;
    for(int i=0;i<n;i++){
        a[e[i][0]].append({e[i][1],l[i]});
        a[e[i][1]].append({e[i][0],l[i]});
    }
    for(int i=pwr[0]=1;i<18;i++)
        pwr[i]=pwr[i-1]*2;
    dept[0]=0;
    dfs(0,-1);
    for(int i=0;i<18;i++) 
        par[0][i]=-1;
    for(int j=0;j<17;j++)
        for(int i=1;i<n;i++)
            par[i][j+1]=par[max(par[i][j],0)][j];
    for(int i=0;i<n;i++){
        p=i;
        q=0;
        for(int j=17;j>=0;j--){
            if(par[p][j]<0) continue;
            else if(dept[i]-dept[par[p][j]]<=x){
                p=par[p][j];
                q+=pwr[j];
                if(dept[i]-dept[p]==x) o=min(o,q); 
            }
        }
    }
    if(o==n) return -1;
    return o;
}

Compilation message

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:30:13: warning: unused variable 'r' [-Wunused-variable]
   30 |     int p,q,r;
      |             ^

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 57.0

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