Submission #782738

#	Time	Username	Problem	Language	Result	Execution time	Memory
782738		vjudge1	Race (IOI11_race)	C++17	0 / 100	5 ms	7380 KiB

race

#include<bits/stdc++.h>
#include "race.h"
using namespace std;
const int N = 2e5+37;
int mi = 1e7, n, k, p;
vector<array<int, 2>> adj[N];
vector<int> vis(N), s(N), vis2(N);
map<int, array<int, 2>> best[2], mp;


void dfs(int v){
    vis[v] = 1;
    int pf=0;
    s[v] = 1;

    for(auto i: adj[v]){
        if(vis2[i[0]]||vis[i[0]]) continue;
        pf++;
        dfs(i[0]); s[v]+=s[i[0]];
    }

}
int dfs2(int v){
    vis[v] = 0;

    for(auto i: adj[v]){
        if(vis2[i[0]]||!vis[i[0]]) continue;
        if(s[i[0]]>=n/2) return dfs2(i[0]);
    }
    return v;
}

void dfs3(int v,  int dist, int z, int f){
   // cout<<v<<" "<<dist<<" "<<z<<"\n";
    if(!mp.count(dist)||mp[dist]>(array<int, 2>){z, v}){
        mp[dist] ={z, v};
    }
    vis[v] = f;
    for(auto i: adj[v]){
        if(vis[i[0]]==f||vis2[i[0]]) continue;
        dfs3(i[0], dist+i[1], z+1, f);
    }
}

void dfs4(int v){
    vis[v] = 1;
    for(auto pf: adj[v]){
        if(vis2[pf[0]]) continue;   
        mp.clear();

        vis[v] = pf[0]+1;
        dfs3(pf[0], pf[1], 1, pf[0]+1);

        for(auto [i, l]: mp){
            if(!best[0].count(i)){
                best[0][i] = l;
            }
            else if(best[0][i]>l){
                swap(l, best[0][i]);
                if(!best[1].count(i)||best[1][i]>l){
                    best[1][i]=l;
                }
            }
            else if(!best[1].count(i)||best[1][i]>l){
                best[1][i]=l;
            }

        }
    }
}


void gh(int v){

    dfs(v); 

    int x = dfs2(v);
    // x is our centroid
    //cout<<x<<"\n";
    dfs4(x);
    for(auto [i, l]: best[0]){
        if(!best[0].count(k-i)||vis[l[1]]==vis[best[0][k-i][1]]){
            if(!best[1].count(k-i)) continue;
            mi=min(mi, best[1][k-i][0]+best[0][i][0]);
        }
        else{
            mi = min(mi, best[0][k-i][0]+best[0][i][0]);
        }
    }

    if(best[0].count(k))
    mi=min(mi, best[0][k][0]);

    vis2[x]=1, p++;
}

int best_path(int N, int K, int a[][2], int l[])
{
    n = N, k = K;

    for(int i= 0; i < n-1; i++){
        int x=a[i][0], y=a[i][1], z=l[i];
        adj[x].push_back({y, z});
        adj[y].push_back({x, z});
    }

    p=1;
    while(p){
        p=0;
        fill(vis.begin(), vis.end(), 0);

        for(int i = 0; i < n; i++)
            if(!vis[i]&&!vis2[i]) gh(i);
    }

    if(mi==1e18) return -1;
    return mi;
}
void f(){
	#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
}
/*
signed main()
{
    //f();
    int n, k; cin >> n >> k;
    int a[n-1][2], l[n-1];
    for(int i=0; i<n-1; i++){
        cin>>a[i][0]>>a[i][1] >> l[i];
    }

   cout<< best_path(n, k, a, l);

}
*/
    

Compilation message (stderr)

race.cpp: In function 'void f()':
race.cpp:121:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |     freopen("in.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
race.cpp:122:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     freopen("out.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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