제출 #287603

#제출 시각아이디문제언어결과실행 시간메모리
287603crossing0ver경주 (Race) (IOI11_race)C++17
0 / 100
6 ms5376 KiB
#include<bits/stdc++.h> //#define int long long #define vi vector<int> #define pii pair<int,int> #define pb push_back #define fi first #define se second //#include "race.h" using namespace std; const int MXN = 1e5+5; vector<pii> adj[MXN]; int n,k,sz[MXN]; bool vis[MXN],bad[MXN]; int calcsize(int v,int p) { sz[v] = 1; for (auto i : adj[v]) { int to = i.fi; if (!bad[to] && to != p) { calcsize(to,v); sz[v] += sz[to]; } } return sz[v]; } pii MN; int SZ; void getcenter(int v,int p) { int mxsz = 0,sum = 0; for (auto i : adj[v]) { int to = i.fi; if (to == p || bad[to]) continue; getcenter(to,v); mxsz = max(mxsz,sz[to]); sum += sz[to]; } int adit = SZ - sum - 1; mxsz = max(mxsz,adit); MN = min(MN,make_pair(mxsz,v)); } const int MAXK = 1e6+6; int dis[MAXK + 5]; int ans = INT_MAX; void get(int v,int p,int depth,int val) { if (val > k) return; if (dis[k-val] && dis[k - val] + depth - 1 < ans) ans = dis[k-val] + depth - 1; for (auto i : adj[v]) { int to = i.fi; if (p != to && !bad[to]) get(to,v,depth+1,val + i.se); } } void upd(int v,int p,int depth,int val,bool flag) { if (dis[val] == 0 || dis[val] > depth) dis[val] = depth; if (flag == 0) dis[val] = 0; for (auto i : adj[v]) { int to = i.fi; if (p!= to && !bad[to]) upd(to,v,depth+1,val + i.se,flag); } } void dfs(int v,int p,int depth,bool keep) { /* int big = -1,mxsz =- 1,money = -1; for (auto i : adj[v]) { int to = i.fi; if (to != p && mxsz < sz[to]) { // mxsz = sz[to]; /// big = to; // money = i.se; } }*/ /* if (big + 1) { get(big,v,depth+1,money); upd(big,v,depth+1,money,1); }*/ for (auto i : adj[v]) { int to = i.fi; if (bad[to]) continue; //if (i == p || i == big) /// continue; get(to,v,2,i.se); upd(to,v,2,i.se,1); } for (auto i : adj[v]) { int to = i.fi; if (to != p && !bad[to]) upd(to,v,depth+1,i.se,0); } } void split(int v){ bool ok = 0; for (auto i : adj[v]) if (!bad[i.fi]) ok = 1; if (ok == 0) return; SZ = calcsize(v,-1); MN = {INT_MAX,0}; // getcenter(v,-1); int center = v; //int center = MN.se; // calcsize(center,-1); dis[0] = 1; dfs(center,-1,1,0); bad[center] = 1; for (auto & i : adj[center]) if (bad[i.fi] == 0) split(i.fi); } int best_path(int n1, int k1, int H[][2], int L[]) { n = n1; k = k1; for (int i = 0; i< n ;i++) { adj[H[i][0]].pb({H[i][1],L[i]}); adj[H[i][1]].pb({H[i][0],L[i]}); } split(0); if (ans == INT_MAX) return -1; return ans-1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...