제출 #297202

#제출 시각아이디문제언어결과실행 시간메모리
297202alexandra_udristoiu경주 (Race) (IOI11_race)C++14
21 / 100
252 ms45672 KiB
#include "race.h" #include<vector> #include<algorithm> #define DIM 100005 #define f first #define s second using namespace std; int viz[DIM], num[DIM], d[1000005]; vector< pair<int, int> > v[DIM]; struct str{ int nod, d, dist, tf; }; vector<str> w[DIM]; void dfs1(int nod, int t){ num[nod] = 1; for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i].f; if(vecin != t && viz[vecin] == 0){ dfs1(vecin, nod); num[nod] += num[vecin]; } } } int findcen(int nod, int t, int k){ for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i].f; if(vecin != t && viz[vecin] == 0){ if(num[vecin] > k / 2){ return findcen(vecin, nod, k); } } } return nod; } void dfs(int nod, int t, int cen, int d, int dist, int fiu){ w[cen].push_back( {nod, d, dist, fiu} ); for(int i = 0; i < v[nod].size(); i++){ int vecin = v[nod][i].f; if(vecin != t && viz[vecin] == 0){ dfs(vecin, nod, cen, d + 1, dist + v[nod][i].s, fiu); } } } void decomp(int nod){ int x, i, vecin; dfs1(nod, -1); x = findcen(nod, -1, num[nod]); viz[x] = 1; for(i = 0; i < v[x].size(); i++){ vecin = v[x][i].f; if(viz[vecin] == 0){ dfs(vecin, x, x, 1, v[x][i].s, vecin); } } for(i = 0; i < v[x].size(); i++){ vecin = v[x][i].f; if(viz[vecin] == 0){ decomp(vecin); } } } int best_path(int n, int k, int h[][2], int lg[]){ int i, j, x, y, sol, ii; for(i = 0; i < n - 1; i++){ x = h[i][0]; y = h[i][1]; v[x].push_back( make_pair(y, lg[i]) ); v[y].push_back( make_pair(x, lg[i]) ); } decomp(0); for(i = 1; i <= k; i++){ d[i] = n; } sol = n; for(i = 0; i < n; i++){ d[0] = 0; for(j = 0; j < w[i].size(); j++){ for(ii = j; ii < w[i].size(); ii++){ if(w[i][j].tf != w[i][ii].tf){ break; } if(w[i][ii].dist <= k){ sol = min(sol, w[i][ii].d + d[ k - w[i][ii].dist ]); } } for(ii = j; ii < w[i].size(); ii++){ if(w[i][j].tf != w[i][ii].tf){ break; } if(w[i][ii].dist <= k){ d[ w[i][ii].dist ] = min(d[ w[i][ii].dist ], w[i][ii].d); } } j = ii - 1; } for(j = 0; j < w[i].size(); j++){ if(w[i][j].dist <= k){ d[ w[i][j].dist ] = n; } } } if(sol == n){ return -1; } return sol; }

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

race.cpp: In function 'void dfs1(int, int)':
race.cpp:16:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
race.cpp: In function 'int findcen(int, int, int)':
race.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int, int, int)':
race.cpp:37:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
race.cpp: In function 'void decomp(int)':
race.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(i = 0; i < v[x].size(); i++){
      |                ~~^~~~~~~~~~~~~
race.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(i = 0; i < v[x].size(); i++){
      |                ~~^~~~~~~~~~~~~
race.cpp: In function 'int best_path(int, int, int (*)[2], int*)':
race.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         for(j = 0; j < w[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
race.cpp:79:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(ii = j; ii < w[i].size(); ii++){
      |                         ~~~^~~~~~~~~~~~~
race.cpp:87:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |             for(ii = j; ii < w[i].size(); ii++){
      |                         ~~~^~~~~~~~~~~~~
race.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<str>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(j = 0; j < w[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...