Submission #964933

#	Time	Username	Problem	Language	Result	Execution time	Memory
964933		Younis_Dwai	Race (IOI11_race)	C++14	21 / 100	3047 ms	41600 KiB

race

#pragma GCC optimize("O3,unroll_loops")
#include "race.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
using namespace std ;
const int MN=1e6+1;
bitset<MN> vis;
int res,k;
vector<int> dp(MN),sz(MN);
vector<pair<int,int>> adj[MN];
void dfs_sz(int node , int par){
     sz[node]=1;
     for(auto u : adj[node]){
         if(vis[u.F] || u.F==par) continue ;
         dfs_sz(u.F,node);
     }
     return ;
}
int  get_centroid(int node ,int par , int d){
     for(auto u : adj[node]){
         if(vis[u.F] || u.F==par || sz[u.F]<=d) continue ;
         return get_centroid(u.F,node,d);
     }
     return node;
}
void dfs_calc(int node, int par , int done ,int dis){
     res=min(res,dp[k-dis]+done);
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_calc(u.F,node,done+1,dis+u.S);
     }
     return ;
}
void dfs_upd(int node , int par , int done , int dis){
     dp[dis]=min(done,dp[dis]);
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_upd(u.F,node,done+1,dis+u.S);
     }
     return ;
}
void dfs_fill(int node , int par ,int dis){
     dp[dis]=1e9;
     for(auto u : adj[node]){
         if(u.F==par || vis[u.F] || dis+u.S>k) continue ;
         dfs_fill(u.F,node,dis+u.S);
     }
     return ;
}
void dfs(int node){
     dfs_sz(node,node);
     int centroid=get_centroid(node,node,sz[node]/2);
     vis[centroid]=1;
     dp[0]=0;
     for(auto u : adj[centroid]){
         if(vis[u.F] || u.S>k) continue ;
         dfs_calc(u.F,centroid,1,u.S);
         dfs_upd(u.F,centroid,1,u.S);
     }
     for(auto u : adj[centroid]){
         if(u.S>k || vis[u.F]) continue ;
         dfs_fill(u.F,centroid,u.S);
     }
     for(auto u :  adj[centroid]){
         if(vis[u.F]) continue ;
         dfs(u.F);
     }
     return ;
}
int best_path(int N, int K, int H[][2], int L[]){
    res=1e9;
    k=K;
    for(int i=0;i<=K;i++) dp[i]=1e9;
    for(int i=0;i<N-1;i++){
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    dfs(0);
    if(res==1e9) return -1;
    else return res;
    return 0;
}

Compilation message (stderr)

race.cpp:1:39: warning: bad option '-funroll_loops' to pragma 'optimize' [-Wpragmas]
    1 | #pragma GCC optimize("O3,unroll_loops")
      |                                       ^
In file included from race.cpp:2:
race.h:1:48: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
    1 | int best_path(int N, int K, int H[][2], int L[]);
      |                                                ^
race.h:1:48: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
race.cpp:13:31: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
   13 | void dfs_sz(int node , int par){
      |                               ^
race.cpp:21:44: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
   21 | int  get_centroid(int node ,int par , int d){
      |                                            ^
race.cpp:28:52: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
   28 | void dfs_calc(int node, int par , int done ,int dis){
      |                                                    ^
race.cpp:36:53: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
   36 | void dfs_upd(int node , int par , int done , int dis){
      |                                                     ^
race.cpp:44:42: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
   44 | void dfs_fill(int node , int par ,int dis){
      |                                          ^
race.cpp:52:18: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
   52 | void dfs(int node){
      |                  ^
race.cpp:72:48: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
   72 | int best_path(int N, int K, int H[][2], int L[]){
      |                                                ^

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