oj.uz

Submission #919137

# Submission time Handle Problem Language Result Execution time Memory
919137 2024-01-31T11:20:38 Z velislavgarkov Highway Tolls (IOI18_highway) C++14
5 / 100
 79 ms 10196 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];
int 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));
    depth[start]=0;
    find_tree(start);
    long long d=(ask(w)-path)/(b-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;
        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<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);
    //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 '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
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3548 KB Output is correct
2 Correct 11 ms 4108 KB Output is correct
3 Correct 69 ms 9020 KB Output is correct
4 Correct 69 ms 8992 KB Output is correct
5 Correct 79 ms 8992 KB Output is correct
6 Correct 74 ms 9036 KB Output is correct
7 Correct 71 ms 9140 KB Output is correct
8 Correct 72 ms 9028 KB Output is correct
9 Correct 73 ms 8828 KB Output is correct
10 Correct 77 ms 9012 KB Output is correct
11 Correct 76 ms 9596 KB Output is correct
12 Correct 65 ms 10196 KB Output is correct
13 Correct 68 ms 9728 KB Output is correct
14 Incorrect 72 ms 9176 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 4620 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 3548 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 4084 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3928 KB Incorrect
2 Halted 0 ms 0 KB -