Submission #130703

# Submission time Handle Problem Language Result Execution time Memory
130703 2019-07-15T23:46:32 Z jovan_b Race (IOI11_race) C++17
9 / 100
839 ms 262144 KB
#include "race.h"
#include <bits/stdc++.h>

using namespace std;

int k;

typedef long long ll;

vector <int> ctree[1000005];
vector <pair <int, int>> graf[1000005];
bool visited[1000005];
bool bio[1000005];
int sz[1000005];
int dir[1000005];
int rnk[1000005];
ll dist[1000005];
int grane[1000005];

int prvi;

void dfs1(int v){
    sz[v] = 1;
    visited[v] = 1;
    for(auto par : graf[v]){
        int c = par.first;
        if(!bio[c] && !visited[c]){
            dfs1(c);
            sz[v] += sz[c];
        }
    }
    visited[v] = 0;
}

int nadji(int v, int n, int par){
    for(auto pr : graf[v]){
        int c = pr.first;
        if(bio[c]) continue;
        if(c == par) continue;
        if(sz[c] > n/2) return nadji(c, n, v);
    }
    return v;
}

int mnn1[1000005];
int mnn2[1000005];

struct strukt{
    int first;
    int second;
    int third;
};

const int INF = 1000001;
int res = INF;

vector <strukt> sons[1000005];

void dfs2(int v, int dis, int brg, int root){
    visited[v] = 1;
    if(v != root) sons[root].push_back({dis, brg, v});
    for(auto pr : graf[v]){
        int c = pr.first;
        int x = pr.second;
        if(!visited[c] && !bio[c]){
            dfs2(c, min(INF, dis+x), brg+1, root);
        }
    }
    visited[v] = 0;
}

void decompose(){
    queue <strukt> q;
    q.push({1, 0, 1});
    while(!q.empty()){
        int v = q.front().first;
        int parent = q.front().second;
        q.pop();
        dfs1(v);
        v = nadji(v, sz[v], 0);
        bio[v] = 1;
        rnk[v] = q.front().third;
        dfs2(v, 0, 0, v);
        if(!parent) prvi = v;
        else{
            dir[v] = parent;
            ctree[parent].push_back(v);
        }
        for(auto pr : graf[v]){
            int c = pr.first;
            if(!bio[c]){
                q.push({c, v, rnk[v]+1});
            }
        }
    }
}

void dfs3(int v){
    vector <int> vec[1000005];
    int cnt = 0;
    for(auto c : ctree[v]){
        dfs3(c);
        sons[c].push_back({0, 0, c});
        cnt++;
        for(auto pr : sons[c]) vec[cnt].push_back(pr.third);
        sons[c].clear();
    }
    for(auto pr : sons[v]){
        ll a = pr.first;
        int b = pr.second;
        int c = pr.third;
        dist[c] = a;
        grane[c] = b;
    }
    for(int i=1; i<=cnt; i++){
        for(auto gg : vec[i]){
            ll a = dist[gg];
            int b = grane[gg];
            if(a == k) res = min(res, b);
            else if(a < k){
                res = min(res, b + mnn1[k-a]);
            }
        }
        for(auto gg : vec[i]){
            ll a = dist[gg];
            ll b = grane[gg];
            if(a > k) continue;
            if(mnn1[a] >= b){
                mnn2[a] = mnn1[a];
                mnn1[a] = b;
            }
            else if(mnn2[a] > b){
                mnn2[a] = b;
            }
        }
    }
    for(auto pr : sons[v]){
        if(pr.first > k) continue;
        mnn1[pr.first] = mnn2[pr.first] = INF;
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    int n = N;
    k = K;
    for(int i=0; i<n-1; i++){
        int a = H[i][0] + 1;
        int b = H[i][1] + 1;
        graf[a].push_back({b, L[i]});
        graf[b].push_back({a, L[i]});
    }
    decompose();
    for(int i=1; i<=n; i++) graf[i].clear();

    for(int i=1; i<=1000000; i++){
        mnn1[i] = mnn2[i] = INF;
    }
    dfs3(prvi);
    if(res == INF) return -1;
    return res;
}

/*int main(){
    int N, K, H[1000005][2], L[1000005];
    cin >> N >> K;
    for(int i=0; i<N; i++){
        cin >> H[i][0] >> H[i][1] >> L[i];
    }
    cout << best_path(N, K, H, L);
}*/
/*
10 6
0 1 3
1 2 2
2 3 2
3 4 3
4 5 2
5 6 2
6 7 1
7 8 2
8 9 2
*/
/*
3 2
0 1 1
1 2 1
*/
# Verdict Execution time Memory Grader output
1 Correct 819 ms 243320 KB Output is correct
2 Correct 749 ms 243216 KB Output is correct
3 Correct 742 ms 243064 KB Output is correct
4 Correct 809 ms 243192 KB Output is correct
5 Correct 742 ms 243192 KB Output is correct
6 Correct 738 ms 243192 KB Output is correct
7 Correct 747 ms 243192 KB Output is correct
8 Correct 749 ms 243192 KB Output is correct
9 Correct 805 ms 243196 KB Output is correct
10 Correct 839 ms 243240 KB Output is correct
11 Correct 731 ms 243064 KB Output is correct
12 Correct 751 ms 243192 KB Output is correct
13 Correct 754 ms 243064 KB Output is correct
14 Correct 734 ms 243192 KB Output is correct
15 Correct 781 ms 243148 KB Output is correct
16 Correct 737 ms 243060 KB Output is correct
17 Correct 744 ms 243092 KB Output is correct
18 Correct 732 ms 243192 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 819 ms 243320 KB Output is correct
2 Correct 749 ms 243216 KB Output is correct
3 Correct 742 ms 243064 KB Output is correct
4 Correct 809 ms 243192 KB Output is correct
5 Correct 742 ms 243192 KB Output is correct
6 Correct 738 ms 243192 KB Output is correct
7 Correct 747 ms 243192 KB Output is correct
8 Correct 749 ms 243192 KB Output is correct
9 Correct 805 ms 243196 KB Output is correct
10 Correct 839 ms 243240 KB Output is correct
11 Correct 731 ms 243064 KB Output is correct
12 Correct 751 ms 243192 KB Output is correct
13 Correct 754 ms 243064 KB Output is correct
14 Correct 734 ms 243192 KB Output is correct
15 Correct 781 ms 243148 KB Output is correct
16 Correct 737 ms 243060 KB Output is correct
17 Correct 744 ms 243092 KB Output is correct
18 Correct 732 ms 243192 KB Output is correct
19 Correct 189 ms 172724 KB Output is correct
20 Correct 821 ms 243168 KB Output is correct
21 Runtime error 536 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 819 ms 243320 KB Output is correct
2 Correct 749 ms 243216 KB Output is correct
3 Correct 742 ms 243064 KB Output is correct
4 Correct 809 ms 243192 KB Output is correct
5 Correct 742 ms 243192 KB Output is correct
6 Correct 738 ms 243192 KB Output is correct
7 Correct 747 ms 243192 KB Output is correct
8 Correct 749 ms 243192 KB Output is correct
9 Correct 805 ms 243196 KB Output is correct
10 Correct 839 ms 243240 KB Output is correct
11 Correct 731 ms 243064 KB Output is correct
12 Correct 751 ms 243192 KB Output is correct
13 Correct 754 ms 243064 KB Output is correct
14 Correct 734 ms 243192 KB Output is correct
15 Correct 781 ms 243148 KB Output is correct
16 Correct 737 ms 243060 KB Output is correct
17 Correct 744 ms 243092 KB Output is correct
18 Correct 732 ms 243192 KB Output is correct
19 Runtime error 525 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 819 ms 243320 KB Output is correct
2 Correct 749 ms 243216 KB Output is correct
3 Correct 742 ms 243064 KB Output is correct
4 Correct 809 ms 243192 KB Output is correct
5 Correct 742 ms 243192 KB Output is correct
6 Correct 738 ms 243192 KB Output is correct
7 Correct 747 ms 243192 KB Output is correct
8 Correct 749 ms 243192 KB Output is correct
9 Correct 805 ms 243196 KB Output is correct
10 Correct 839 ms 243240 KB Output is correct
11 Correct 731 ms 243064 KB Output is correct
12 Correct 751 ms 243192 KB Output is correct
13 Correct 754 ms 243064 KB Output is correct
14 Correct 734 ms 243192 KB Output is correct
15 Correct 781 ms 243148 KB Output is correct
16 Correct 737 ms 243060 KB Output is correct
17 Correct 744 ms 243092 KB Output is correct
18 Correct 732 ms 243192 KB Output is correct
19 Correct 189 ms 172724 KB Output is correct
20 Correct 821 ms 243168 KB Output is correct
21 Runtime error 536 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -