oj.uz

Submission #919092

# Submission time Handle Problem Language Result Execution time Memory
919092 2024-01-31T08:38:16 Z velislavgarkov Highway Tolls (IOI18_highway) C++14
5 / 100
 129 ms 8836 KB 
#include "highway.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
vector <pair <int,int> > v[MAXN], dist;
vector <int> w;
int edge;
long long a, b, path;
int n;
void find_tree(int x, int par) {
    for (auto i:v[x]) {
        if (i.second==edge) continue;
        if (i.first==par) continue;
        w[i.second]=1;
        find_tree(i.first,x);
    }
}
void dfs(int x, int par, int d) {
    for (auto i:v[x]) {
        if (i.second==edge) continue;
        if (i.first==par) continue;
        if (d==1) {
            dist.push_back(i);
            continue;
        }
        dfs(i.first,x,d-1);
    }
}
int find_one(int start) {
    for (int i=0;i<n-1;i++) w[i]=0;
    find_tree(start,start);
    long long d=(ask(w)-path)/(b-a);
    if (d==0) return 1/0;
    if (!dist.empty()) dist.clear();
    dfs(start,start,d);
    if (dist.empty()) return 1/0;
    int l, r, mid;
    l=0; r=dist.size()-1;
    while (l<r) {
        mid=(l+r)/2;
        for (int i=0;i<n-1;i++) w[i]=0;
        for (int i=l;i<=mid;i++) w[dist[i].second]=1;
        int cur=ask(w);
        if (cur==path) l=mid+1;
        else r=mid;
    }
    return dist[l].first;
}
void find_pair (int N, vector <int> U, vector <int> V, int A, int B) {
    n=N; a=A; b=B;
    w.resize(n-1);
    for (int i=0;i<n-1;i++) {
        v[U[i]].push_back({V[i],i});
        v[V[i]].push_back({U[i],i});
    }
    for (int i=0;i<n-1;i++) w[i]=0;
    path=ask(w);
    //cout << path << endl;
    edge=-1;
    int ans1, ans2;
    /*
    int l, r, mid;
    l=0; r=n-1;
    while (l<r) {
        mid=(l+r)/2;
        for (int i=0;i<n-1;i++) w[i]=0;
        for (int i=l;i<=mid;i++) w[i]=1;
        int cur=ask(w);
        if (cur==path) l=mid+1;
        else r=mid;
    }
    edge=l;
    //cout << U[edge] << ' ' << V[edge] << endl;
    ans1=find_one(U[edge]);
    ans2=find_one(V[edge]);*/
    ans1=0;
    ans2=find_one(0);
    answer(ans1,ans2);    
}

Compilation message

highway.cpp: In function 'int find_one(int)':
highway.cpp:34:23: warning: division by zero [-Wdiv-by-zero]
   34 |     if (d==0) return 1/0;
      |                      ~^~
highway.cpp:37:31: warning: division by zero [-Wdiv-by-zero]
   37 |     if (dist.empty()) return 1/0;
      |                              ~^~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2848 KB Output is correct
2 Correct 10 ms 3416 KB Output is correct
3 Correct 85 ms 8128 KB Output is correct
4 Correct 84 ms 8140 KB Output is correct
5 Correct 109 ms 8112 KB Output is correct
6 Correct 66 ms 7968 KB Output is correct
7 Correct 77 ms 8028 KB Output is correct
8 Correct 97 ms 8148 KB Output is correct
9 Correct 85 ms 7940 KB Output is correct
10 Correct 73 ms 8112 KB Output is correct
11 Correct 70 ms 8384 KB Output is correct
12 Correct 69 ms 8836 KB Output is correct
13 Correct 129 ms 8492 KB Output is correct
14 Incorrect 71 ms 8364 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3596 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 1 ms 2848 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 Incorrect 8 ms 3160 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 3160 KB Incorrect
2 Halted 0 ms 0 KB -