Submission #170024

#	Time	Username	Problem	Language	Result	Execution time	Memory
170024		alexandra_udristoiu	Highway Tolls (IOI18_highway)	C++14	51 / 100	287 ms	12420 KiB

highway

#include<iostream>
#include<vector>
#include "highway.h"
#define f first
#define s second
#define DIM 130005
using namespace std;
static int t[2][DIM], niv[2][DIM], viz[2][DIM], m, p[2][DIM], nr[2], n, cd[DIM];
static pair<int, int> w[DIM];
static vector<int> r, v[DIM];
void bfs(int i, int srs){
   int st, dr, j, nod, vecin;
   viz[i][srs] = 1;
   cd[1] = srs;
   st = dr = 1;
   while(st <= dr){
        nod = cd[st];
        st++;
        p[i][nod] = ++nr[i];
        for(j = 0; j < v[nod].size(); j++){
            vecin = v[nod][j];
            if(viz[i][vecin] == 0){
                cd[++dr] = vecin;
                niv[i][vecin] = 1 + niv[i][nod];
                t[i][vecin] = nod;
                viz[i][vecin] = 1;
            }
        }
   }
}
int solve(int ind){
    int i, st, dr, mid;
    for(i = 0; i < m; i++){
        if(t[ind][ w[i].s ] == w[i].f){
            swap(w[i].f, w[i].s);
        }
        r[i] = 0;
    }
    long long sum = ask(r);
    for(i = 0; i < m; i++){
        r[i] = 1;
    }
    st = 1;
    dr = n;
    while(st < dr){
        mid = (st + dr) / 2;
        for(i = 0; i < m; i++){
            if(t[ind][ w[i].f ] == w[i].s && niv[ind][ w[i].f ] < niv[1 - ind][ w[i].f ]){
                if(p[ind][ w[i].f ] > mid && p[ind][ w[i].s ] <= dr){
                    r[i] = 1;
                }
                else{
                    r[i] = 0;
                }
            }
            else{
                r[i] = 0;
            }
        }
        if(ask(r) > sum){
            st = mid + 1;
        }
        else{
            dr = mid;
        }
    }
    for(int i = 1; i <= n; i++){
        if(p[ind][i] == st){
            return i;
        }
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int a, int b){
    n = N;
    int i, st, dr, mid, x, y;
    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);
        r[i] = 0;
    }
    sum = ask(r);
    st = 0;
    dr = m - 1;
    while(st < dr){
        mid = (st + dr) / 2;
        for(i = 0; i < m; i++){
            if(i >= st && i <= mid){
                r[i] = 1;
            }
            else{
                r[i] = 0;
            }
        }
        if(ask(r) > sum){
            dr = mid;
        }
        else{
            st = mid + 1;
        }
    }
    bfs(0, w[st].f);
    bfs(1, w[st].s);
    x = solve(0);
    y = solve(1);
    answer(x - 1, y - 1);
}

Compilation message (stderr)

highway.cpp: In function 'void bfs(int, int)':
highway.cpp:20:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j = 0; j < v[nod].size(); j++){
                    ~~^~~~~~~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:76:20: warning: unused variable 'cost' [-Wunused-variable]
     long long sum, cost;
                    ^~~~
highway.cpp: In function 'int solve(int)':
highway.cpp:72:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31