Submission #169321

#	Time	Username	Problem	Language	Result	Execution time	Memory
169321		alexandra_udristoiu	Highway Tolls (IOI18_highway)	C++14	51 / 100	476 ms	262148 KiB

highway

#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, ok[DIM];
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 != 0 && ok[nod] == 1){
        return;
    }
    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;
        ok[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);
}

Compilation message (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:35: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:111:10: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
     p[x] = 0;
     ~~~~~^~~
highway.cpp:136:11: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     answer(x - 1, y - 1);
     ~~~~~~^~~~~~~~~~~~~~

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