Submission #250084

#	Time	Username	Problem	Language	Result	Execution time	Memory
250084		ant101	Highway Tolls (IOI18_highway)	C++14	Compilation error	0 ms	0 KiB

highway

#include "highway.h"
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 90005;

vector<int> gph[MAXN];

lint cut_ask(int m, vector<int> &c, vector<int> &u, vector<int> &v){
    bitset<MAXN> vis;
    for(auto &i : c) vis[i] = 1;
    vector<int> query(m);
    for(int i=0; i<m; i++) if(vis[u[i]] != vis[v[i]]) query[i] = 1;
    return ask(query);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    if (!((A == 1 && B == 2) || U.size() == N-1)) {
        return;
    }
    int M = U.size();
    for(int i=0; i<M; i++){
        gph[U[i]].emplace_back(V[i]);
        gph[V[i]].emplace_back(U[i]);
    }
    vector<int> v(M);
    lint stdist = ask(v) / A;
    int s = 0, e = M - 1;
    while(s != e){
        int m = (s + e) / 2;
        fill(v.begin() + m + 1, v.end(), 0);
        fill(v.begin(), v.begin() + m + 1, 1);
        if(ask(v) != A * stdist) e = m;
        else s = m + 1;
    }
    vector<int> bord[2], dist(N, 1e9);
    queue<pi> que;
    que.emplace(0, U[s]);
    que.emplace(1, V[s]);
    dist[U[s]] = dist[V[s]] = 0;
    while(!que.empty()){
        auto x = que.front(); que.pop();
        bord[x.first].push_back(x.second);
        for(auto &i : gph[x.second]){
            if(dist[i] > dist[x.second] + 1){
                dist[i] = dist[x.second] + 1;
                que.emplace(x.first, i);
            }
        }
    }
    int S = -1, T = -1;
    for(int i=0; i<2; i++){
        int s = 0, e = (int)bord[i].size() - 1;
        while(s != e){
            int m = (s + e + 1) / 2;
            vector<int> C(bord[i].begin() + m, bord[i].end());
            if(cut_ask(M, C, U, V) != stdist * A) s = m;
            else e = m - 1;
        }
        if(i) S = bord[i][s];
        else T = bord[i][s];
    }
    answer(S, T);
}

Compilation message (stderr)

highway.cpp: In function 'lint cut_ask(int, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
highway.cpp:27:5: error: 'bitset' was not declared in this scope
     bitset<MAXN> vis;
     ^~~~~~
highway.cpp:27:5: note: suggested alternative: 'fd_set'
     bitset<MAXN> vis;
     ^~~~~~
     fd_set
highway.cpp:27:18: error: 'vis' was not declared in this scope
     bitset<MAXN> vis;
                  ^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:35:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (!((A == 1 && B == 2) || U.size() == N-1)) {
                                 ~~~~~~~~~^~~~~~