제출 #964933

#제출 시각아이디문제언어결과실행 시간메모리
964933Younis_Dwai경주 (Race) (IOI11_race)C++14
21 / 100
3047 ms41600 KiB
#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; }

컴파일 시 표준 에러 (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[]){
      |                                                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...