oj.uz

Submission #799570

# Submission time Handle Problem Language Result Execution time Memory
799570 2023-07-31T16:05:11 Z Khizri Highway Tolls (IOI18_highway) C++17
51 / 100
 335 ms 262144 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=1e5+5;
int n,m,a,b,mx,sz,dis;
vector<int>que;
vector<pii>vt[mxn];
vector<pii>nodes;
void find_dep(int u,int p,int dep){
    mx=max(mx,dep);
    for(pii pp:vt[u]){
        int v=pp.F;
        if(v!=p){
            find_dep(v,u,dep+1);
        }
    }
}
void dfs(int u,int p,int dep){
    for(pii pp:vt[u]){
        int v=pp.F,idx=pp.S;
        if(v==p) continue;
        if(dep+1<=sz){
            que[idx]=1;
        }
        else{
            que[idx]=0;
        }
        dfs(v,u,dep+1);
    }
}
void add_nodes(int u,int p,int dep){
    for(pii pp:vt[u]){
        int v=pp.F,idx=pp.S;
        if(v!=p){
            if(dep+1==dis) nodes.pb({v,idx});
            add_nodes(v,u,dep+1);
        }
    }
}
ll check(int x){
    sz=x;
    dfs(1,-1,0);
    ll res=ask(que);
    return res;
}
void find_pair(int N, vector<int> ux, vector<int> vx, int A, int B) {
    n=N;
    a=A,b=B;
    m=ux.size();
    for(int i=0;i<m;i++){
        int u=ux[i]+1,v=vx[i]+1;
        vt[u].pb({v,i});
        vt[v].pb({u,i});
    }
    for(int i=0;i<m;i++){
        que.pb(1);
    }
    ll cost=ask(que);
    find_dep(1,-1,0);
    int l=0,r=mx;
    while(l<=r){
        int m=(l+r)/2;
        if(check(m)<cost){
            l=m+1;
        }
        else{
            r=m-1;
        }
    }
    ll cost2=cost/b*a;
    dis=l;
    add_nodes(1,-1,0);
    l=0,r=nodes.size()-1;
    while(l<=r){
        int mm=(l+r)/2;
        for(int i=0;i<m;i++){
            que[i]=0;
        }
        for(int i=l;i<=mm;i++){
            que[nodes[i].S]=1;
        }
        ll res=ask(que);
        if(res>cost2){
            r=mm-1;
        }
        else{
            l=mm+1;
        }
    }
    r++;
    int root=nodes[r].F;
    ll cnt=cost/b;
    nodes.clear();
    dis=cnt;
    add_nodes(root,-1,0);
    l=0,r=nodes.size()-1;
    while(l<=r){
        int mm=(l+r)/2;
        for(int i=0;i<m;i++){
            que[i]=0;
        }
        for(int i=l;i<=mm;i++){
            que[nodes[i].S]=1;
        }
        ll res=ask(que);
        if(res>cost2){
            r=mm-1;
        }
        else{
            l=mm+1;
        }
    }
    r++;
    int root2=nodes[r].F;
    answer(root-1,root2-1);
}
/*
g++ highway.cpp grader.cpp ; .\a.exe
8 7 1 2 5 6
0 1
0 2
1 3
1 4
4 6
6 7
2 5
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 1 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 1 ms 2640 KB Output is correct
7 Correct 1 ms 2640 KB Output is correct
8 Correct 1 ms 2640 KB Output is correct
9 Correct 2 ms 2640 KB Output is correct
10 Correct 1 ms 2640 KB Output is correct
11 Correct 2 ms 2640 KB Output is correct
12 Correct 1 ms 2652 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 11 ms 3356 KB Output is correct
3 Correct 106 ms 7980 KB Output is correct
4 Correct 113 ms 7996 KB Output is correct
5 Correct 106 ms 7992 KB Output is correct
6 Correct 111 ms 7948 KB Output is correct
7 Correct 99 ms 7972 KB Output is correct
8 Correct 85 ms 7988 KB Output is correct
9 Correct 80 ms 7988 KB Output is correct
10 Correct 129 ms 8092 KB Output is correct
11 Correct 150 ms 8996 KB Output is correct
12 Correct 179 ms 10008 KB Output is correct
13 Correct 142 ms 9176 KB Output is correct
14 Correct 151 ms 9360 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3868 KB Output is correct
2 Correct 22 ms 5336 KB Output is correct
3 Correct 23 ms 6648 KB Output is correct
4 Correct 114 ms 14304 KB Output is correct
5 Correct 99 ms 14364 KB Output is correct
6 Correct 96 ms 14324 KB Output is correct
7 Correct 102 ms 14372 KB Output is correct
8 Correct 73 ms 14344 KB Output is correct
9 Correct 79 ms 14364 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2640 KB Output is correct
2 Correct 11 ms 3280 KB Output is correct
3 Correct 80 ms 6904 KB Output is correct
4 Correct 123 ms 8000 KB Output is correct
5 Correct 120 ms 7944 KB Output is correct
6 Correct 109 ms 7968 KB Output is correct
7 Correct 89 ms 8008 KB Output is correct
8 Correct 100 ms 8012 KB Output is correct
9 Correct 104 ms 7952 KB Output is correct
10 Correct 118 ms 8020 KB Output is correct
11 Correct 221 ms 8888 KB Output is correct
12 Correct 156 ms 9916 KB Output is correct
13 Correct 277 ms 9392 KB Output is correct
14 Correct 220 ms 9828 KB Output is correct
15 Correct 114 ms 7944 KB Output is correct
16 Correct 109 ms 7944 KB Output is correct
17 Correct 197 ms 9508 KB Output is correct
18 Correct 153 ms 9684 KB Output is correct
19 Correct 84 ms 7952 KB Output is correct
20 Correct 199 ms 10300 KB Output is correct
21 Correct 96 ms 9924 KB Output is correct
22 Correct 97 ms 9924 KB Output is correct
23 Correct 100 ms 8692 KB Output is correct
24 Correct 116 ms 9324 KB Output is correct
25 Correct 283 ms 13708 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 335 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 242 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -