oj.uz

Submission #1049249

# Submission time Handle Problem Language Result Execution time Memory
1049249 2024-08-08T15:27:24 Z beaconmc Race (IOI11_race) C++14
31 / 100
 1390 ms 199332 KB 
#include "race.h"
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

const ll maxn = 200005;
const ll INF = 1000000000;

vector<vector<ll>> edges[maxn];
ll par[maxn];
ll centpar[maxn];
ll depth[maxn];
ll realdepth[maxn];
ll ancc[maxn][20];
bool visited[maxn];
ll sub[maxn];
ll sus[maxn];

ll anc(ll a, ll x){
    if (a==0) return 0;
    if (x==0) return par[a];
    if (ancc[a][x] != -1) return ancc[a][x];
    return ancc[a][x] = anc(anc(a,x-1),x-1);
}

ll lca(ll a, ll b){
    if (depth[a] < depth[b]) swap(a,b);
    FORNEG(i,19,-1) if (depth[anc(a, i)] >= depth[b]) a = anc(a,i);
    if (a==b) return a;
    FORNEG(i,19,-1) if (anc(a,i) != anc(b,i)) a = anc(a,i), b = anc(b,i);
    return par[a];
}

void initdfs(ll a,ll p, ll d, ll dd){
    par[a] = p;
    depth[a] = d;
    realdepth[a] = dd;
    for (auto&i : edges[a]){
        if (i[0] != p) initdfs(i[0], a, d+1, dd+i[1]);
    }
}

ll centroid(ll root, ll a, ll p){
    for (auto&i : edges[a]){
        if (!visited[i[0]] && i[0] != p && sub[i[0]] > sub[root]/2) return centroid(root, i[0], a);
    }
    return a;
}
void dfs(ll a, ll p){
    sub[a] = 1;
    for (auto&i : edges[a]){

        if(i[0] != p && !visited[i[0]]) dfs(i[0], a), sub[a] += sub[i[0]];
    }
}
void build(ll a, ll p){

    dfs(a,p);
    ll cent = centroid(a, a, p);


    centpar[cent] = p;
    visited[cent] = 1;
    for (auto&i : edges[cent]){
        if (!visited[i[0]]) build(i[0], cent);
    }
}

vector<array<ll,3>> dists[maxn];

int best_path(int N, int K, int H[][2], int L[])
{
    FOR(i,0,maxn) par[i] = -1, centpar[i] = -1, par[i] -1, depth[i] = -1, realdepth[i] = -1,visited[i] = 0,dists[i].clear(),edges[i].clear(), sus[i] = INF;
    FOR(i,0,maxn)FOR(j,0,20) ancc[i][j] = -1;
    
    
    FOR(i,0,N-1){

        edges[H[i][0]].push_back({H[i][1], L[i]});
        edges[H[i][1]].push_back({H[i][0], L[i]});
    }

    
    initdfs(0,-1,0,0);
    dfs(0,-1);

    build(0,-1);



    

    FOR(i,0,N){
        ll temp = centpar[i];
        ll prev = i;
        ll cnt = 0;
        while (temp != -1){
            cnt++;

            ll idk = lca(temp,i);
            ll cur = depth[temp] + depth[i] - depth[idk]*2;
 
           
            ll dist = realdepth[temp] + realdepth[i] - realdepth[idk]*2;

            dists[temp].push_back({prev, dist, cur });
            
            prev = temp;
            temp = centpar[temp];
        }
    }
    ll ans = INF;
    FOR(i,0,N){
        sort(dists[i].begin(), dists[i].end());
        vector<ll> used;
        used.push_back(0);
        
        sus[0] = 0;
        vector<array<ll, 3>> cache;
        if (dists[i].size()) cache.push_back(dists[i][0]), used.push_back(dists[i][0][1]);;
        FOR(j,1,dists[i].size()){
            used.push_back(dists[i][j][1]);
            if (dists[i][j][0] != dists[i][j-1][0]){
                for (auto&k : cache){
                    if (k[1] < K) sus[k[1]] = min(sus[k[1]], k[2]);

                }
            }
            ll req = K - dists[i][j][1];
            if (0<=req && req <= K) ans = min(ans, sus[req] + dists[i][j][2]);
            cache.push_back(dists[i][j]);
        }
        for (auto&k : used) if (0<=k && k<=K) sus[k] = INF;

    }

    if (ans >= INF) return -1;
    else return ans;

}

Compilation message

race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:77:56: warning: right operand of comma operator has no effect [-Wunused-value]
   77 |     FOR(i,0,maxn) par[i] = -1, centpar[i] = -1, par[i] -1, depth[i] = -1, realdepth[i] = -1,visited[i] = 0,dists[i].clear(),edges[i].clear(), sus[i] = INF;
      |                                                 ~~~~~~~^~
race.cpp:5:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
  125 |         FOR(j,1,dists[i].size()){
      |             ~~~~~~~~~~~~~~~~~~~  
race.cpp:125:9: note: in expansion of macro 'FOR'
  125 |         FOR(j,1,dists[i].size()){
      |         ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 54364 KB Output is correct
2 Correct 6 ms 54192 KB Output is correct
3 Correct 7 ms 54372 KB Output is correct
4 Correct 6 ms 54360 KB Output is correct
5 Correct 7 ms 54364 KB Output is correct
6 Correct 6 ms 54364 KB Output is correct
7 Correct 6 ms 54364 KB Output is correct
8 Correct 6 ms 54280 KB Output is correct
9 Correct 7 ms 54364 KB Output is correct
10 Correct 6 ms 54360 KB Output is correct
11 Correct 7 ms 54364 KB Output is correct
12 Correct 7 ms 54388 KB Output is correct
13 Correct 6 ms 54364 KB Output is correct
14 Correct 6 ms 54364 KB Output is correct
15 Correct 6 ms 54372 KB Output is correct
16 Correct 6 ms 54364 KB Output is correct
17 Correct 6 ms 54360 KB Output is correct
18 Correct 6 ms 54364 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 54364 KB Output is correct
2 Correct 6 ms 54192 KB Output is correct
3 Correct 7 ms 54372 KB Output is correct
4 Correct 6 ms 54360 KB Output is correct
5 Correct 7 ms 54364 KB Output is correct
6 Correct 6 ms 54364 KB Output is correct
7 Correct 6 ms 54364 KB Output is correct
8 Correct 6 ms 54280 KB Output is correct
9 Correct 7 ms 54364 KB Output is correct
10 Correct 6 ms 54360 KB Output is correct
11 Correct 7 ms 54364 KB Output is correct
12 Correct 7 ms 54388 KB Output is correct
13 Correct 6 ms 54364 KB Output is correct
14 Correct 6 ms 54364 KB Output is correct
15 Correct 6 ms 54372 KB Output is correct
16 Correct 6 ms 54364 KB Output is correct
17 Correct 6 ms 54360 KB Output is correct
18 Correct 6 ms 54364 KB Output is correct
19 Correct 6 ms 54364 KB Output is correct
20 Correct 6 ms 54376 KB Output is correct
21 Correct 7 ms 54620 KB Output is correct
22 Incorrect 7 ms 54744 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 54364 KB Output is correct
2 Correct 6 ms 54192 KB Output is correct
3 Correct 7 ms 54372 KB Output is correct
4 Correct 6 ms 54360 KB Output is correct
5 Correct 7 ms 54364 KB Output is correct
6 Correct 6 ms 54364 KB Output is correct
7 Correct 6 ms 54364 KB Output is correct
8 Correct 6 ms 54280 KB Output is correct
9 Correct 7 ms 54364 KB Output is correct
10 Correct 6 ms 54360 KB Output is correct
11 Correct 7 ms 54364 KB Output is correct
12 Correct 7 ms 54388 KB Output is correct
13 Correct 6 ms 54364 KB Output is correct
14 Correct 6 ms 54364 KB Output is correct
15 Correct 6 ms 54372 KB Output is correct
16 Correct 6 ms 54364 KB Output is correct
17 Correct 6 ms 54360 KB Output is correct
18 Correct 6 ms 54364 KB Output is correct
19 Correct 304 ms 103636 KB Output is correct
20 Correct 289 ms 103004 KB Output is correct
21 Correct 281 ms 103120 KB Output is correct
22 Correct 260 ms 98556 KB Output is correct
23 Correct 288 ms 111204 KB Output is correct
24 Correct 149 ms 91804 KB Output is correct
25 Correct 534 ms 121456 KB Output is correct
26 Correct 349 ms 123036 KB Output is correct
27 Correct 330 ms 128092 KB Output is correct
28 Correct 1347 ms 199332 KB Output is correct
29 Correct 1390 ms 198164 KB Output is correct
30 Correct 335 ms 127164 KB Output is correct
31 Correct 326 ms 128880 KB Output is correct
32 Correct 507 ms 128504 KB Output is correct
33 Correct 997 ms 172276 KB Output is correct
34 Correct 964 ms 169788 KB Output is correct

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 54364 KB Output is correct
2 Correct 6 ms 54192 KB Output is correct
3 Correct 7 ms 54372 KB Output is correct
4 Correct 6 ms 54360 KB Output is correct
5 Correct 7 ms 54364 KB Output is correct
6 Correct 6 ms 54364 KB Output is correct
7 Correct 6 ms 54364 KB Output is correct
8 Correct 6 ms 54280 KB Output is correct
9 Correct 7 ms 54364 KB Output is correct
10 Correct 6 ms 54360 KB Output is correct
11 Correct 7 ms 54364 KB Output is correct
12 Correct 7 ms 54388 KB Output is correct
13 Correct 6 ms 54364 KB Output is correct
14 Correct 6 ms 54364 KB Output is correct
15 Correct 6 ms 54372 KB Output is correct
16 Correct 6 ms 54364 KB Output is correct
17 Correct 6 ms 54360 KB Output is correct
18 Correct 6 ms 54364 KB Output is correct
19 Correct 6 ms 54364 KB Output is correct
20 Correct 6 ms 54376 KB Output is correct
21 Correct 7 ms 54620 KB Output is correct
22 Incorrect 7 ms 54744 KB Output isn't correct
23 Halted 0 ms 0 KB -