oj.uz

Submission #919146

# Submission time Handle Problem Language Result Execution time Memory
919146 2024-01-31T11:27:55 Z velislavgarkov Highway Tolls (IOI18_highway) C++14
51 / 100
 108 ms 13548 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 path;
    int n;
    long long a, b;
    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);
        int 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;
            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<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;
        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;
        int ans1, ans2;
        ans1=find_one(U[edge]);
        ans2=find_one(V[edge]);
        answer(ans1,ans2);    
    }

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 2796 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 2796 KB Output is correct
7 Correct 2 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
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2844 KB Output is correct
2 Correct 13 ms 3400 KB Output is correct
3 Correct 94 ms 8544 KB Output is correct
4 Correct 95 ms 8108 KB Output is correct
5 Correct 85 ms 8112 KB Output is correct
6 Correct 89 ms 7972 KB Output is correct
7 Correct 79 ms 8124 KB Output is correct
8 Correct 105 ms 7932 KB Output is correct
9 Correct 83 ms 7944 KB Output is correct
10 Correct 108 ms 8144 KB Output is correct
11 Correct 81 ms 8172 KB Output is correct
12 Correct 92 ms 8876 KB Output is correct
13 Correct 85 ms 8404 KB Output is correct
14 Correct 108 ms 8696 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3656 KB Output is correct
2 Correct 18 ms 4704 KB Output is correct
3 Correct 19 ms 5340 KB Output is correct
4 Correct 62 ms 10380 KB Output is correct
5 Correct 72 ms 10200 KB Output is correct
6 Correct 62 ms 11760 KB Output is correct
7 Correct 70 ms 11356 KB Output is correct
8 Correct 63 ms 10332 KB Output is correct
9 Correct 82 ms 10508 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2844 KB Output is correct
2 Correct 14 ms 3360 KB Output is correct
3 Correct 63 ms 6780 KB Output is correct
4 Correct 86 ms 8016 KB Output is correct
5 Correct 107 ms 8076 KB Output is correct
6 Correct 73 ms 8144 KB Output is correct
7 Correct 76 ms 7928 KB Output is correct
8 Correct 73 ms 7904 KB Output is correct
9 Correct 84 ms 8104 KB Output is correct
10 Correct 84 ms 8128 KB Output is correct
11 Correct 84 ms 8236 KB Output is correct
12 Correct 93 ms 8744 KB Output is correct
13 Correct 103 ms 8548 KB Output is correct
14 Correct 93 ms 8696 KB Output is correct
15 Correct 90 ms 7900 KB Output is correct
16 Correct 101 ms 7912 KB Output is correct
17 Correct 90 ms 8296 KB Output is correct
18 Correct 86 ms 8576 KB Output is correct
19 Correct 93 ms 7916 KB Output is correct
20 Correct 75 ms 8932 KB Output is correct
21 Correct 76 ms 9604 KB Output is correct
22 Correct 70 ms 9600 KB Output is correct
23 Correct 86 ms 8860 KB Output is correct
24 Correct 85 ms 9048 KB Output is correct
25 Correct 105 ms 13548 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 3168 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3120 KB Incorrect
2 Halted 0 ms 0 KB -