oj.uz

Submission #826466

# Submission time Handle Problem Language Result Execution time Memory
826466 2023-08-15T15:37:18 Z ALeonidou Highway Tolls (IOI18_highway) C++17
51 / 100
 212 ms 10964 KB 
#include <bits/stdc++.h>
#include "highway.h"
    
using namespace std;
    
#define ll int
typedef vector <ll> vi;
typedef pair <ll,ll > ii;
typedef vector <ii> vii;
#define sz(x) (ll)x.size()
#define pb push_back
#define F first
#define S second
#define MID ((l+r)/2)
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define dbg2(x,y) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<endl;
#define dbg3(x,y,z) cout<<#x<<": "<<x<<" "<<#y<<": "<<y<<" "<<#z<<": "<<z<<endl;
    
void tabb(ll n){
    for (ll i= 0; i<n; i++) cout<<"\t";
}
    
void printVct(vi &v){
    for (ll i=0; i<sz(v); i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}
    
void printVctPair(vii &v){
    for (ll i=0; i<sz(v); i++){
        cout<<"("<<v[i].F<<","<<v[i].S<<") ";
    }
    cout<<endl;
}
    
void printVct2D(vector<vi> &adj){
    for (ll i=0; i<sz(adj); i++){
        cout<<i<<": ";
        for (ll j =0; j<sz(adj[i]); j++){
            cout<<"("<<adj[i][j]<<"),";
        }
        cout<<endl;
    }
    cout<<endl;
}
    
void printVctPair2D(vector<vii> &adj){
    for (ll i=0; i<sz(adj); i++){
        for (ll j =0; j<sz(adj[i]); j++){
            cout<<"("<<adj[i][j].F<<","<<adj[i][j].S<<"),";
        }
        cout<<endl;
    }
    cout<<endl;
}
    
vector <vii> adj;
ll n,m;
long long b;   //all light case value

ll solve(ll root){
    queue <ll> q;
    vii dis(n);
    for (ll i =0; i<n; i++)
        dis[i] = ii(-1, i);
    dis[root].F = 0;
    vi par(n, -1);
    q.push(root);
    while (!q.empty()){
        ll u= q.front();
        q.pop();
        for (ll i = 0; i<sz(adj[u]); i++){
            if (dis[adj[u][i].F].F == -1){
                q.push(adj[u][i].F);
                dis[adj[u][i].F].F = dis[u].F + 1;
                par[adj[u][i].F] = adj[u][i].S;
            }
        }
    }

    sort(dis.rbegin(), dis.rend());
    // cout<<"dis:";
    // printVctPair(dis);
    // cout<<"par:";
    // printVct(par);

    vi v;
    ll l = 0, r = n-1, mid;
    while (l < r){
        mid = MID;
        // dbg3(l,r,mid);

        v.assign(m, 0);
        // printVct(v);
        for (ll i= 0; i<=mid; i++){
            ll tmp = par[dis[i].S];
            if (tmp != -1) v[tmp] = 1;
        }

        long long c =ask(v);

        if (c > b){
            r = mid;
        }
        else{
            l = mid+1;
        }
    }            
    return dis[l].S;
}
    
void find_pair(int N, vi V, vi U, int A,int B) {
    n = N; m = sz(U);
    adj.assign(n, vii());
    for (ll i=0; i<m ;i++){
        adj[U[i]].pb(ii(V[i], i));
        adj[V[i]].pb(ii(U[i], i));
    }
    vi v(m, 0);  
    b = ask(v);
    
    ll l = 0, r = m-1, mid;
    while (l < r){
        mid = MID;
        v.assign(m, 0);
        for (ll i = 0; i<=mid; i++) 
            v[i] = 1;
        long long c = ask(v);
        if (c > b) r = mid;
        else l = mid+1;
    }
    ll p = U[l];
    // dbg(p);
    
    ll s = solve(p);
    // dbg(s);
    // cout<<endl<<endl<<endl;
    ll t = solve(s);
    //dbg2(s,t);
    answer(s, t);
}
    
/*
14 13 2 5 0 13
0 1
1 5
1 2
2 3
1 4
5 7
7 8
5 6
3 12
3 11
2 9
9 10
9 13

14 13 2 5 3 10
0 1
1 5
1 2
2 3
1 4
5 7
7 8
5 6
3 12
3 11
2 9
9 10
9 13
    
*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 0 ms 304 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 0 ms 308 KB Output is correct
12 Correct 0 ms 208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 12 ms 1232 KB Output is correct
3 Correct 141 ms 9004 KB Output is correct
4 Correct 100 ms 9036 KB Output is correct
5 Correct 149 ms 9008 KB Output is correct
6 Correct 120 ms 8996 KB Output is correct
7 Correct 106 ms 8992 KB Output is correct
8 Correct 102 ms 9064 KB Output is correct
9 Correct 121 ms 9016 KB Output is correct
10 Correct 143 ms 9000 KB Output is correct
11 Correct 104 ms 8400 KB Output is correct
12 Correct 119 ms 8508 KB Output is correct
13 Correct 125 ms 8416 KB Output is correct
14 Correct 105 ms 8408 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1104 KB Output is correct
2 Correct 16 ms 2088 KB Output is correct
3 Correct 40 ms 3012 KB Output is correct
4 Correct 77 ms 8404 KB Output is correct
5 Correct 135 ms 8412 KB Output is correct
6 Correct 98 ms 8400 KB Output is correct
7 Correct 98 ms 8420 KB Output is correct
8 Correct 103 ms 8404 KB Output is correct
9 Correct 71 ms 8416 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 10 ms 1232 KB Output is correct
3 Correct 77 ms 7208 KB Output is correct
4 Correct 100 ms 9000 KB Output is correct
5 Correct 123 ms 9004 KB Output is correct
6 Correct 121 ms 9004 KB Output is correct
7 Correct 126 ms 9020 KB Output is correct
8 Correct 117 ms 9000 KB Output is correct
9 Correct 98 ms 9000 KB Output is correct
10 Correct 115 ms 9016 KB Output is correct
11 Correct 113 ms 8424 KB Output is correct
12 Correct 97 ms 8412 KB Output is correct
13 Correct 153 ms 8412 KB Output is correct
14 Correct 109 ms 8408 KB Output is correct
15 Correct 101 ms 9012 KB Output is correct
16 Correct 135 ms 9016 KB Output is correct
17 Correct 111 ms 8476 KB Output is correct
18 Correct 123 ms 8408 KB Output is correct
19 Correct 116 ms 9100 KB Output is correct
20 Correct 94 ms 8432 KB Output is correct
21 Correct 93 ms 9496 KB Output is correct
22 Correct 135 ms 9504 KB Output is correct
23 Correct 103 ms 9292 KB Output is correct
24 Correct 127 ms 9216 KB Output is correct
25 Correct 112 ms 8548 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1280 KB Output is correct
2 Correct 15 ms 1344 KB Output is correct
3 Correct 155 ms 9416 KB Output is correct
4 Correct 129 ms 9936 KB Output is correct
5 Incorrect 212 ms 10964 KB Output is incorrect: {s, t} is wrong.
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1276 KB Output is correct
2 Correct 13 ms 1320 KB Output is correct
3 Partially correct 133 ms 9480 KB Output is partially correct
4 Correct 162 ms 9660 KB Output is correct
5 Correct 122 ms 9924 KB Output is correct
6 Incorrect 150 ms 10964 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -