oj.uz

Submission #919143

# Submission time Handle Problem Language Result Execution time Memory
919143 2024-01-31T11:25:16 Z velislavgarkov Highway Tolls (IOI18_highway) C++14
0 / 100
 18 ms 8432 KB 
#include "highway.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN=1e5+10;
vector <pair <int,int> > v[MAXN], dist;
vector <int> w;
bool used[MAXN];
long long depth[MAXN], par[MAXN];
int edge;
long long a, b, path;
int n;
void find_tree(int x) {
    used[x]=true;
    for (auto i:v[x]) {
        if (i.second==edge) continue;
        if (used[i.first]) continue;
        w[i.second]=1;
        depth[i.first]=depth[x]+1;
        par[i.first]=i.second;
        find_tree(i.first);
    }
}
int find_one(int start) {
    for (int i=0;i<n-1;i++) w[i]=0;
    memset(used,false,sizeof(used));
    memset(depth,0,sizeof(depth));
    find_tree(start);
    long long d=path/a;
    if (d==0) return start;
    if (!dist.empty()) dist.clear();
    for (int i=0;i<n;i++) {
        if (depth[i]==d) dist.push_back({i,par[i]});
    }
    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;
        long long 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<U.size();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);
    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;
        long long cur=ask(w);
        if (cur==path) l=mid+1;
        else r=mid;
    }
    edge=l;
    ans1=find_one(U[edge]);
    ans2=find_one(V[edge]);
    answer(ans1,ans2);    
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for (int i=0;i<U.size();i++) {
      |                  ~^~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4276 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 Runtime error 7 ms 8432 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 5392 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 2 ms 4336 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 4696 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 4868 KB Incorrect
2 Halted 0 ms 0 KB -