oj.uz

Submission #919090

# Submission time Handle Problem Language Result Execution time Memory
919090 2024-01-31T08:31:15 Z velislavgarkov Highway Tolls (IOI18_highway) C++14
5 / 100
 108 ms 8816 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 start;
    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: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 1 ms 2792 KB Output is correct
2 Correct 1 ms 2788 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 2 ms 2792 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2788 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2648 KB Output is correct
9 Correct 2 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 2844 KB Output is correct
2 Correct 9 ms 3400 KB Output is correct
3 Correct 75 ms 8120 KB Output is correct
4 Correct 75 ms 8108 KB Output is correct
5 Correct 70 ms 8136 KB Output is correct
6 Correct 77 ms 7972 KB Output is correct
7 Correct 66 ms 8028 KB Output is correct
8 Correct 72 ms 8144 KB Output is correct
9 Correct 66 ms 7952 KB Output is correct
10 Correct 85 ms 8112 KB Output is correct
11 Correct 108 ms 8388 KB Output is correct
12 Correct 88 ms 8816 KB Output is correct
13 Correct 68 ms 8484 KB Output is correct
14 Incorrect 91 ms 8352 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 14 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 2844 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 12 ms 3416 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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