Submission #260104

#	Time	Username	Problem	Language	Result	Execution time	Memory
260104		aggu_01000101	Race (IOI11_race)	C++14	21 / 100	3086 ms	37132 KiB

race

#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <map>
#include <bits/stdc++.h>
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define int long long
#define INF 10000000000000000
#define MOD 1000000007
using namespace std;
const int N = 200005;
const int K = 1000005;
vector<pair<int, int>> adj[N];
vector<int> adj1[N];
int tb = 0;
int t = 0;
int tin[N], tout[N];
int depth[N], edges[N];
bool chosen[N];
int h[N][20];
int s[N], size = 0;
int ans = INF;
int LCA_DFS(int i, int par, int dep, int edep){
    tin[i] = ++t;
    depth[i] = dep;
    edges[i] = edep;
    if(i!=par){
        h[i][0] = par;
        for(int j = 1;j<=19;j++){
            if(h[i][j-1] != -1) h[i][j] = h[h[i][j-1]][j-1];
        }
    }
    for(pair<int, int> j: adj[i]){
        if(j.first == par) continue;
        LCA_DFS(j.first, i, dep + j.second, edep+1);
    }
    tout[i] = ++t;
}
bool anc(int u, int v){
    if((tin[u] <= tin[v]) && (tout[u] >= tout[v])) return true;
    return false;
}
int LCA(int u, int v){
    if(anc(u, v)){
        return u;
    }
    if(anc(v, u)) return v;
    for(int i = 19;i>=0;i--){
        if(h[u][i]!=-1 && !anc(h[u][i], v)) u = h[u][i];
    }
    return h[u][0];
}
pair<int, int> dist(int u, int v){
    return {(depth[u] + depth[v] - 2*depth[LCA(u, v)]), (edges[u] + edges[v] - 2*edges[LCA(u, v)])};
}
int dfs(int i, int par){
    size++;
    s[i] = 1;
    for(pair<int, int> j: adj[i]){
        if(j.first == par) continue;
        s[i] += dfs(j.first, i);
    }
    return s[i];
}
int centroid(int i, int par){
    for(pair<int, int> j: adj[i]){
        if(j.first == par) continue;
        if(chosen[j.first]) continue;
        if(s[j.first] < ((size+1)/2)) continue;
        return centroid(j.first, i);
    }
    return i;
}
int decompose(int i, int par){
    size = 0;
    dfs(i, par);
    int pp = centroid(i, par);
    chosen[pp] = true;
    for(pair<int, int> j: adj[pp]){
        if(chosen[j.first]) continue;
        int child = decompose(j.first, pp);
        //cout<<pp<<" is a parent of "<<child<<endl;
        adj1[pp].push_back(child);
    }
    return pp;
}
int findans(int i, int src, int mine[], map<int, bool> &vis){
    pair<int, int> d = dist(i, src);
    if(d.first<=tb) if(vis[tb - d.first]) ans = min(ans, d.second + mine[tb - d.first]);
    for(int j: adj1[i]){
        findans(j, src, mine, vis);
    }
}
int update(int i, int src, int mine[], map<int, bool> &vis){
    pair<int, int> d = dist(i, src);
    //cout<<"Distance from "<<i<<" to "<<src<<" is "<<d.first<<endl;
    if(d.first<=tb){
        if(!vis[d.first]) mine[d.first] = d.second;
        else mine[d.first] = min(mine[d.first], d.second);
        vis[d.first] = true;
    }
    for(int j: adj1[i]){
        update(j, src, mine, vis);
    }
}
int getans(int i, int mine[], map<int, bool> &vis){
    for(int j: adj1[i]){
        findans(j, i, mine, vis);
        update(j, i, mine, vis);
    }
}
signed best_path(signed n, signed k, signed hh[][2], signed l[]){
    tb = k;
    ans = INF;
    for(int i = 0;i<(n-1);i++){
        adj[hh[i][0]+1].push_back({hh[i][1]+1, l[i]});
        adj[hh[i][1]+1].push_back({hh[i][0]+1, l[i]});
    }
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<20;j++) h[i][j] = -1;
    }
    LCA_DFS(1, 1, 0, 0);
    int cr = decompose(1, 1);
    //cr is the new root of our tree
    for(int i = 1;i<=n;i++){
        int mine[K];
        map<int, bool> vis;
        mine[0] = 0;
        vis[0] = true;
        getans(i, mine, vis);
    }
    if(ans>=INF) ans = -1;
    return ans;
}
/*signed main(){
    signed n, k;
    cin>>n>>k;
    signed bitch[n-1][2];
    signed l[n-1];
    for(int i =0 ;i<(n-1);i++) cin>>bitch[i][0]>>bitch[i][1]>>l[i];
    cout<<best_path(n, k, bitch, l)<<endl;
}*/
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
 */
/*
3 3
0 1 1
1 2 1
 */

Compilation message (stderr)

race.cpp: In function 'long long int LCA_DFS(long long int, long long int, long long int, long long int)':
race.cpp:43:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'long long int findans(long long int, long long int, long long int*, std::map<long long int, bool>&)':
race.cpp:98:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'long long int update(long long int, long long int, long long int*, std::map<long long int, bool>&)':
race.cpp:110:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'long long int getans(long long int, long long int*, std::map<long long int, bool>&)':
race.cpp:116:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:128:9: warning: unused variable 'cr' [-Wunused-variable]
     int cr = decompose(1, 1);
         ^~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57