제출 #169314

#제출 시각아이디문제언어결과실행 시간메모리
169314alexandra_udristoiu통행료 (IOI18_highway)C++14
18 / 100
466 ms262148 KiB
#include<iostream> #include<vector> #include "highway.h" #define f first #define s second #define DIM 130005 using namespace std; static int t[DIM], p[DIM], nr; static pair<int, int> w[DIM]; static vector<int> r, v[DIM]; static void dfs(int nod, int tt){ t[nod] = tt; int i, vecin; for(i = 0; i < v[nod].size(); i++){ vecin = v[nod][i]; if(vecin != tt){ p[vecin] = ++nr; } } for(i = 0; i < v[nod].size(); i++){ vecin = v[nod][i]; if(vecin != tt){ dfs(vecin, nod); } } } static void dfs2(int nod, int tt, int niv, int num){ if(niv == num){ p[nod] = ++nr; } else{ for(int i = 0; i < v[nod].size(); i++){ if(v[nod][i] != tt){ dfs2(v[nod][i], nod, niv + 1, num); } } } } void find_pair(int n, vector<int> U, vector<int> V, int a, int b){ int m, i, st, dr, mid, num, niv, x, y, nod; long long sum, cost; m = U.size(); r.resize(m); for(i = 0; i < m; i++){ w[i] = make_pair(U[i] + 1, V[i] + 1); v[ w[i].f ].push_back(w[i].s); v[ w[i].s ].push_back(w[i].f); } dfs(1, 0); for(i = 0; i < m; i++){ if(t[ w[i].s ] == w[i].f){ swap(w[i].f, w[i].s); } r[i] = 0; } sum = ask(r); st = 1; dr = n - 1; while(st < dr){ mid = (st + dr) / 2; for(i = 0; i < m; i++){ if(p[ w[i].f ] > mid && p[ w[i].f ] <= dr){ r[i] = 1; } else{ r[i] = 0; } } if(ask(r) > sum){ st = mid + 1; } else{ dr = mid; } } for(i = 2; i <= n; i++){ if(p[i] == st){ x = i; } } num = sum / a; for(i = x; i != 0; i = t[i]){ p[i] = -1; } for(i = 0; i < m; i++){ if(p[ w[i].f ] == -1){ r[i] = 1; } else{ r[i] = 0; } } cost = ask(r); niv = (cost - sum) / (b - a); num -= niv; for(i = x; niv > 0; i = t[i], niv--); nod = i; if(num == 0){ answer(nod - 1, x - 1); return; } for(i = 1; i <= n; i++){ p[i] = 0; } nr = 0; dfs2(nod, t[nod], 0, num); p[x] = 0; st = 1; dr = nr; while(st < dr){ mid = (st + dr) / 2; for(i = 0; i < m; i++){ if(p[ w[i].f ] > mid && p[ w[i].f ] <= dr){ r[i] = 1; } else{ r[i] = 0; } } if(ask(r) > sum){ st = mid + 1; } else{ dr = mid; } } for(i = 2; i <= n; i++){ if(p[i] == st){ y = i; } } answer(x - 1, y - 1); }

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

highway.cpp: In function 'void dfs(int, int)':
highway.cpp:14:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < v[nod].size(); i++){
                ~~^~~~~~~~~~~~~~~
highway.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i = 0; i < v[nod].size(); i++){
                ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'void dfs2(int, int, int, int)':
highway.cpp:32:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < v[nod].size(); i++){
                        ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:107:10: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     p[x] = 0;
     ~~~~~^~~
highway.cpp:132:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     answer(x - 1, y - 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...