Submission #297202

#	Time	Username	Problem	Language	Result	Execution time	Memory
297202		alexandra_udristoiu	Race (IOI11_race)	C++14	21 / 100	252 ms	45672 KiB

race

#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;
}

Compilation message (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++){
      |                    ~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57