oj.uz

Submission #919141

# Submission time Handle Problem Language Result Execution time Memory
919141 2024-01-31T11:24:49 Z velislavgarkov Highway Tolls (IOI18_highway) C++14
12 / 100
 103 ms 11148 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);
    //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;
        long long 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 2 ms 4280 KB Output is correct
2 Correct 2 ms 4284 KB Output is correct
3 Correct 2 ms 4184 KB Output is correct
4 Correct 2 ms 4284 KB Output is correct
5 Correct 1 ms 4184 KB Output is correct
6 Correct 1 ms 4276 KB Output is correct
7 Correct 2 ms 4184 KB Output is correct
8 Correct 2 ms 4184 KB Output is correct
9 Correct 2 ms 4276 KB Output is correct
10 Correct 2 ms 4184 KB Output is correct
11 Correct 2 ms 4184 KB Output is correct
12 Correct 2 ms 4184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4332 KB Output is correct
2 Correct 10 ms 4940 KB Output is correct
3 Correct 86 ms 9788 KB Output is correct
4 Correct 100 ms 9788 KB Output is correct
5 Correct 92 ms 9772 KB Output is correct
6 Correct 76 ms 9632 KB Output is correct
7 Correct 78 ms 9684 KB Output is correct
8 Correct 103 ms 9796 KB Output is correct
9 Correct 77 ms 9596 KB Output is correct
10 Correct 66 ms 9776 KB Output is correct
11 Correct 83 ms 10380 KB Output is correct
12 Correct 86 ms 11148 KB Output is correct
13 Correct 72 ms 10640 KB Output is correct
14 Correct 100 ms 9960 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 5296 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 4492 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 4864 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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