oj.uz

Submission #1115738

# Submission time Handle Problem Language Result Execution time Memory
1115738 2024-11-20T21:36:19 Z lambd47 Race (IOI11_race) C++14
0 / 100
 157 ms 177736 KB 
#include "race.h"
#include<bits/stdc++.h>

using namespace std;

const int MOD=1e9+7;
const int MX=2e5+6;
vector<pair<int,int>> adj[MX];
vector<pair<int,int>> vec;
vector<int> limpa;
bool marc[MX];
int sz[MX];
int p[100*MX];

int k;
int n;

int dfssz(int node, int pai){
    sz[node]=1;
    for(auto [a,_]: adj[node]){
        if(a==pai || marc[a])continue;
        sz[node]+=dfssz(a,node);
    }
    return sz[node]; 

}

int findcent(int node, int s, int pai){
    for(auto [a,_]: adj[node]){
        if(a==pai || marc[a])continue;
        if(2*sz[a]>s)return findcent(a,s,node);
    }
    return node;
}

void dfs(int node, int pai, int d,int prof){
    vec.push_back({d,prof});
    limpa.push_back(d);
    for(auto [a,w]:adj[node]){
        if(a==pai || marc[a])continue;
        dfs(a,node,d+w,prof+1);
    }
}

int resp;


void centroidDecomp(int node){
    int s=dfssz(node,node);
    node=findcent(node,s,node);

    marc[node]=1; 
    p[0]=0;
    
    for(auto [a,w]: adj[node]){
        if(marc[a])continue;
        vec.clear();
        dfs(a,node,w,1);
        for(auto [d,prof]:vec){
            if(k>=d && p[k-d]!=MOD){
                resp=min(resp,prof+p[k-d]);
            }
        }
        for(auto [d,prof]:vec){
            p[d]=min(p[d],prof);
        }

    }
    for(auto a: limpa){
        p[a]=MOD;
    }
    limpa.clear();
    for(auto [a,_]:adj[node]){
        if(!marc[a])
        centroidDecomp(a);
    }


}





int best_path(int N, int K, int H[][2], int L[])
{
    k=K;
    n=N;
    resp=MOD;
    for(int i=1;i<100*MX;i++)p[i]=MOD;
    for(int i=0;i<n;i++){
        int a=H[i][0],b=H[i][1];
        adj[a].push_back({b,L[i]});
        adj[b].push_back({a,L[i]});
    }
    centroidDecomp(0);
    if(resp==MOD)return -1;



    return resp;
}

Compilation message

race.cpp: In function 'int dfssz(int, int)':
race.cpp:20:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for(auto [a,_]: adj[node]){
      |              ^
race.cpp: In function 'int findcent(int, int, int)':
race.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   29 |     for(auto [a,_]: adj[node]){
      |              ^
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     for(auto [a,w]:adj[node]){
      |              ^
race.cpp: In function 'void centroidDecomp(int)':
race.cpp:55:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |     for(auto [a,w]: adj[node]){
      |              ^
race.cpp:59:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   59 |         for(auto [d,prof]:vec){
      |                  ^
race.cpp:64:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   64 |         for(auto [d,prof]:vec){
      |                  ^
race.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for(auto [a,_]:adj[node]){
      |              ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 87880 KB Output is correct
2 Correct 47 ms 87700 KB Output is correct
3 Correct 50 ms 87680 KB Output is correct
4 Correct 50 ms 87868 KB Output is correct
5 Runtime error 157 ms 177736 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 87880 KB Output is correct
2 Correct 47 ms 87700 KB Output is correct
3 Correct 50 ms 87680 KB Output is correct
4 Correct 50 ms 87868 KB Output is correct
5 Runtime error 157 ms 177736 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 87880 KB Output is correct
2 Correct 47 ms 87700 KB Output is correct
3 Correct 50 ms 87680 KB Output is correct
4 Correct 50 ms 87868 KB Output is correct
5 Runtime error 157 ms 177736 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 87880 KB Output is correct
2 Correct 47 ms 87700 KB Output is correct
3 Correct 50 ms 87680 KB Output is correct
4 Correct 50 ms 87868 KB Output is correct
5 Runtime error 157 ms 177736 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -