oj.uz

Submission #286388

# Submission time Handle Problem Language Result Execution time Memory
286388 2020-08-30T10:59:18 Z Vimmer Highway Tolls (IOI18_highway) C++14
0 / 100
 254 ms 262148 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2688 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2688 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 4224 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2688 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 254 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 254 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -