oj.uz

Submission #296105

# Submission time Handle Problem Language Result Execution time Memory
296105 2020-09-10T09:19:53 Z Autoratch Highway Tolls (IOI18_highway) C++14
12 / 100
 294 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 9e4 + 1;

int n,m,a,b;
vector<int> adj[N],ass;
vector<pair<int,int> > res;
vector<tuple<int,int,int> > ed;
int lv[N];

long long ash(vector<int> x)
{
    ass.assign(m,0);
    for(int y : x) ass[y] = 1;
    return ask(ass);
}

void dfs(int u,int p)
{
    lv[u] = lv[p]+1;
    for(int v : adj[u]) if(v!=p) dfs(v,u);
}

void find_pair(int N, vector<int> U, vector<int> V, int A,int B) 
{
    n = N,m = U.size();
    a = A,b = B;
    for(int i = 0;i < m;i++)
    {
        int a = U[i],b = V[i];
        a++,b++;
        adj[a].push_back(b);
        adj[b].push_back(a);
        ed.push_back({i,a,b});
        ed.push_back({i,b,a});
    }
    vector<int> tmp;
    long long dist = ash(tmp)/a;
    dfs(1,0);
    for(auto [id,x,y] : ed) if(lv[x]==dist+1 and lv[y]<lv[x])
    {
        res.push_back({id,x});
    }
    int l = 0,r = res.size();
    r--;
    while(l<r)
    {
        int m = (l+r)/2;
        tmp.clear();
        for(int i = l;i <= m;i++) tmp.push_back(res[i].first);
        long long ret = ash(tmp);
        if(ret==dist*a) l = m+1;
        else r = m;
    }
    answer(0,res[l].second-1);
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:42:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |     for(auto [id,x,y] : ed) if(lv[x]==dist+1 and lv[y]<lv[x])
      |              ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2432 KB Output is correct
2 Correct 2 ms 2432 KB Output is correct
3 Correct 2 ms 2432 KB Output is correct
4 Correct 2 ms 2432 KB Output is correct
5 Correct 2 ms 2432 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2432 KB Output is correct
8 Correct 2 ms 2432 KB Output is correct
9 Correct 2 ms 2432 KB Output is correct
10 Correct 2 ms 2432 KB Output is correct
11 Correct 2 ms 2432 KB Output is correct
12 Correct 2 ms 2432 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2560 KB Output is correct
2 Correct 13 ms 3328 KB Output is correct
3 Correct 148 ms 9768 KB Output is correct
4 Correct 131 ms 9880 KB Output is correct
5 Correct 131 ms 9764 KB Output is correct
6 Correct 146 ms 9752 KB Output is correct
7 Correct 134 ms 9768 KB Output is correct
8 Correct 177 ms 9880 KB Output is correct
9 Correct 153 ms 9640 KB Output is correct
10 Correct 150 ms 9768 KB Output is correct
11 Correct 138 ms 10536 KB Output is correct
12 Correct 132 ms 10920 KB Output is correct
13 Correct 131 ms 10536 KB Output is correct
14 Correct 136 ms 10152 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2560 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 294 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 269 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -