Submission #286388

#	Time	Username	Problem	Language	Result	Execution time	Memory
286388		Vimmer	Highway Tolls (IOI18_highway)	C++14	0 / 100	254 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
//#include "grader.h"

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 100005
#define M ll(998244353)
#define inf 1e9 + 1e9

using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <ll, 3> a3;
typedef array <ll, 4> a4;

vector <pair <int, int> > g[N];

vector <int> vr;

void dfs(int v, int p)
{
    for (auto it : g[v])
    {
        if (it.F == p) continue;

        vr.pb(it.S);

        dfs(it.F, v);
    }
}
void find_pair (int n, vector <int> u, vector <int> v, int a, int b)
{
    bool f = 1;

    for (int i = 0; i < n - 1; i++)
    {
        if (u[i] != i || v[i] != i + 1) f = 0;

        g[u[i]].pb({v[i], i});

        g[v[i]].pb({u[i], i});
    }

    dfs(0, -1);

    int l = 0, r = n - 2;

    while (l < r)
    {
        int md = (l + r) >> 1;

        vector <int> a; a.clear();

        for (int i = 0; i < n - 1; i++) a.pb(0);

        ll sm = ask(a);

        for (int i = md; i < n - 1; i++) a[i] = 1;

        ll smr = ask(a);

        if (sm != smr) r = md - 1;
         else l = md;
    }

    answer(0, v[l]);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:46:10: warning: variable 'f' set but not used [-Wunused-but-set-variable]
   46 |     bool f = 1;
      |          ^

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