oj.uz

Submission #919096

# Submission time Handle Problem Language Result Execution time Memory
919096 2024-01-31T08:41:19 Z velislavgarkov Highway Tolls (IOI18_highway) C++14
5 / 100
 93 ms 8828 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);
    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;
    }
    if (l>dist.size()) return 1/0;
    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:47:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     if (l>dist.size()) return 1/0;
      |         ~^~~~~~~~~~~~
highway.cpp:47:32: warning: division by zero [-Wdiv-by-zero]
   47 |     if (l>dist.size()) return 1/0;
      |                               ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2788 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2792 KB Output is correct
5 Correct 1 ms 2648 KB Output is correct
6 Correct 1 ms 2792 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 2792 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 1 ms 2840 KB Output is correct
2 Correct 9 ms 3400 KB Output is correct
3 Correct 91 ms 8348 KB Output is correct
4 Correct 93 ms 8356 KB Output is correct
5 Correct 82 ms 8636 KB Output is correct
6 Correct 70 ms 7968 KB Output is correct
7 Correct 72 ms 8032 KB Output is correct
8 Correct 67 ms 8160 KB Output is correct
9 Correct 79 ms 7940 KB Output is correct
10 Correct 83 ms 8348 KB Output is correct
11 Correct 70 ms 8616 KB Output is correct
12 Correct 89 ms 8828 KB Output is correct
13 Correct 92 ms 8480 KB Output is correct
14 Incorrect 74 ms 8536 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 8 ms 3600 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 9 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 -