제출 #29421

#제출 시각아이디문제언어결과실행 시간메모리
29421Nikefor경주 (Race) (IOI11_race)C++98
9 / 100
3051 ms19952 KiB
#include "race.h" #include<bits/stdc++.h> #define inf 1<<22 using namespace std; int globalMin = inf; int target; int W[1000001]; set<int> used; vector< pair<int,int> > adj[200001]; void centroid(int n); int sizer(int n, int road) { int sum = 0; for(int i=0; i<adj[n].size(); i++) { if(used.find(adj[n][i].first)==used.end() and (adj[n][i].second!=road)) sum+=sizer(adj[n][i].first, adj[n][i].second); } return sum+1; } int best_path(int N, int K, int H[][2], int L[]) { target = K; for(int i=0; i<N-1; i++) { int v1 = H[i][0], v2 = H[i][1]; adj[v1].push_back(make_pair(v2, i)); adj[v2].push_back(make_pair(v1, i)); } for(int i=0; i<N-1; i++) W[i] = L[i]; centroid(0); return globalMin<inf?globalMin:-1; } int A[200002]; int tmp[200002]; void DFS(int c, int road, int cost, int edge) { if(tmp[cost]>edge) tmp[cost] = edge; if(tmp[cost]+A[target-cost]<globalMin) globalMin = tmp[cost]+A[target-cost]; for(int i =0; i< adj[c].size(); i++) { if(used.find(adj[c][i].first)!=used.end()) continue; if(adj[c][i].second!=road and ((cost+W[adj[c][i].second])<=target) ) DFS(adj[c][i].first, adj[c][i].second, cost+W[adj[c][i].second], edge+1); } } void centroid(int n) { if( sizer(n, -1)<2 ) return; // int c = centroidibul(int n); int c = n; int kol = adj[c].size(); for(int i=1; i<target+1; i++) A[i] = tmp[i] = inf; A[0] = tmp[0]=0; for(int i= 0; i<kol; i++) { if(used.find(adj[c][i].first)!=used.end() ) continue; for(int j=1; j<=target; j++) tmp[j] = inf; if(W[adj[c][i].second] <= target )DFS(adj[c][i].first, adj[c][i].second, W[adj[c][i].second], 1); // for(int j=1; j<target; j++) if((tmp[j]+A[target-j])<globalMin) globalMin = tmp[j]+A[target-j]; for(int j=1; j<target; j++) if(tmp[j]<A[j]) A[j] = tmp[j]; } used.insert(c); for(int i=0; i<kol; i++) if(used.find(adj[c][i].first)==used.end() ) centroid(adj[c][i].first); }

컴파일 시 표준 에러 (stderr) 메시지

race.cpp: In function 'int sizer(int, int)':
race.cpp:13:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<adj[n].size(); i++) {
                  ~^~~~~~~~~~~~~~
race.cpp: In function 'void DFS(int, int, int, int)':
race.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i =0; i< adj[c].size(); i++) {
                   ~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...