oj.uz

Submission #1030140

# Submission time Handle Problem Language Result Execution time Memory
1030140 2024-07-21T21:19:05 Z kl0989e Race (IOI11_race) C++17
0 / 100
 3 ms 6748 KB 
#include <bits/stdc++.h>
#include "race.h"
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=2e5+10;
vector<vector<pi>> graph(maxn);
vi sze(maxn);
vi cen_num(maxn,-1);
int ans=1e9;
int needed;
unordered_map<int,int> added;
unordered_map<int,int> now;

void dfs2(int cur, int prev, int len, int dist) {
    if (now.find(len)==now.end() || now[len]>dist) {
        if (len==needed) {
            ans=min(ans,len);
        }
        else {
            now[len]=dist;
        }
    }
    for (auto [to,w]:graph[cur]) {
        if (to==prev || len+w>needed || cen_num[to]!=-1) {
            continue;
        }
        dfs2(to,cur,len+w,dist+1);
    }
}

void dfs(int cur, int prev, int num, int cur_sze) {
    sze[cur]=1;
    bool is_cen=1;
    for (auto [to,_]:graph[cur]) {
        if (to==prev || cen_num[to]!=-1) {
            continue;
        }
        dfs(to,cur,num,cur_sze);
        if (cen_num[cur]!=-1) {
            return;
        }
        sze[cur]+=sze[to];
        if (sze[to]>cur_sze/2) {
            is_cen=0;
        }
    }
    if (!is_cen || cur_sze-sze[cur]>cur_sze/2) {
        return;
    }
    cen_num[cur]=num;
    for (auto [to,w]:graph[cur]) {
        if (cen_num[to]!=-1 || w>needed) {
            continue;
        }
        dfs2(to,cur,w,1);
        if (now.size()>added.size()) {
            swap(now,added);
        }
        for (auto [a,b]:now) {
            if (added.find(needed-a)!=added.end() && added[needed-a]+b<ans) {
                ans=added[needed-a]+b;
            }
        }
        for (auto [a,b]:now) {
            if (added.find(a)==added.end() || added[a]>b) {
                added[a]=b;
            }
        }
        now.clear();
    }
    added.clear();
    for (auto [to,_]:graph[cur]) {
        if (cen_num[to]!=-1) {
            continue;
        }
        if (prev==to) {
            dfs(to,cur,num+1,cur_sze-sze[cur]);
        }
        else {
            dfs(to,cur,num+1,sze[to]);
        }
    }
}

int best_path(int n, int k, int edge[][2], int len[]) {
    for (int i=0; i<n-1; i++) {
        graph[edge[i][0]].pb({edge[i][1],len[i]});
        graph[edge[i][1]].pb({edge[i][0],len[i]});
    }
    needed=k;
    dfs(0,-1,0,n);
    return (ans==1e9?-1:ans);
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6592 KB Output is correct
6 Correct 3 ms 6500 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Incorrect 3 ms 6492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6592 KB Output is correct
6 Correct 3 ms 6500 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Incorrect 3 ms 6492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6592 KB Output is correct
6 Correct 3 ms 6500 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Incorrect 3 ms 6492 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6592 KB Output is correct
6 Correct 3 ms 6500 KB Output is correct
7 Correct 3 ms 6492 KB Output is correct
8 Incorrect 3 ms 6492 KB Output isn't correct
9 Halted 0 ms 0 KB -