oj.uz

Submission #425373

# Submission time Handle Problem Language Result Execution time Memory
425373 2021-06-13T00:42:11 Z arneves Highway Tolls (IOI18_highway) C++17
51 / 100
 269 ms 14160 KB 
#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second

vector<pair<int,int>> adj[150000];
int ver[150000];
int are[150000];
int visitados[150000];
int contador;

void dfs(int s){

    for(auto u: adj[s]){
        if(visitados[u.f]==0){
            visitados[u.f]++;
            are[u.s]=contador;
            ver[contador]=u.f;
            contador++;
            dfs(u.f);
        }
    }
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {


    int M=U.size();
    if(M==N-1||1){
        vector<int> w(M,0);

        ll tamanho=ask(w);

        for(int i=0; i<M; i++){

            adj[U[i]].push_back({V[i],i});
            adj[V[i]].push_back({U[i],i});
        }

        int l=0, r=N-2, m;

        while(l<r){

            m=(l+r)/2;

            for(int i=0; i<M; i++){
                if(i<=m) w[i]=1;
                else w[i]=0;
            }

            if(ask(w)!=tamanho){
                r=m;
            }else{
                l=m+1;
            }
        }

//partimos o gráfico pela aresta l, logo os
//vertices das duas arvores que sobram serao
//os extremos da aresta l;
        int a=U[l], b=V[l];

        memset(visitados, 0, sizeof(visitados));
        memset(ver,-1, sizeof(ver));
        memset(are,-1,sizeof(are));

        visitados[b]=visitados[a]=1;
        contador=0;
        dfs(a);

        int ans1, ans2;

        l=-1;
        r=N-2;
        while(l<r){

            m=(l+r+1)/2;

            for(int i=0; i<M; i++){
                if(are[i]>=m) w[i]=1;
                else w[i]=0;
                //cout<<w[i]<<' ';
            }
            //cout<<'\n';
            if(ask(w)!=tamanho){
                l=m;
            }else{
                r=m-1;
            }
        }
        ans1=l;
        if(ans1==-1) ans1=a;
        else ans1= ver[ans1];

        memset(visitados, 0, sizeof(visitados));
        memset(ver,-1, sizeof(ver));
        memset(are,-1,sizeof(are));

        visitados[b]=visitados[a]=1;
        contador=0;
        dfs(b);

        l=-1;
        r=N-2;
        while(l<r){

            m=(l+r+1)/2;

            for(int i=0; i<M; i++){
                if(are[i]>=m) w[i]=1;
                else w[i]=0;
                //cout<<w[i]<<' ';
            }
            //cout<<'\n';
            if(ask(w)!=tamanho){
                l=m;
            }else{
                r=m-1;
            }
        }
        ans2=l;
        if(ans2==-1) ans2=b;
        else ans2= ver[ans2];

        //for(int i=0; i<M; i++) cout<<are[i]<<' '; cout<<'\n';
        //for(int i=0; i<M; i++) cout<<ver[i]<<' '; cout<<'\n';
        //for(auto u: are) cout<<u<<' '; cout<<'\n';
        answer(ans1, ans2);
        //cout<<"->"<<ans1<<' '<<ans2<<'\n';
    }else{

    }
}
/*
5 4 16 20 1 4
0 1
1 2
2 3
3 4
****************
5 4 16 20 1 3
0 1
1 2
2 3
3 4
****************
5 4 16 20 0 2
0 1
1 2
2 3
3 4
****************
5 4 16 20 3 4
0 1
1 2
2 3
3 4
*/
/*
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {

    int M=U.size();

    ll tamanho;

    vector<int> w(M,0);

    ll ultima=ask(w), atual;

    tamanho=(ultima/A);
    w[0]=1;

    int l=0, r=N-2, m;

    while(l<r){
        m=(l+r)/2;

        for(int i=0; i<M; i++){
            if(i<=m){
                w[i]=0;
            }else{
                w[i]=1;
            }
            //cout<<w[i]<<' ';
        }
        //cout<<"->"<<m<<'\n';
        atual=ask(w);

        if(atual==ultima){
            r=m-1;
        }else if(atual/B==ultima/A){
            l=m+1;
        }else{
            r=m;
        }
    }

    //cout<<l<<' '<<l+tamanho<<'\n';
    answer(l, l+tamanho);
}
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5576 KB Output is correct
2 Correct 17 ms 6060 KB Output is correct
3 Correct 171 ms 10704 KB Output is correct
4 Correct 183 ms 10700 KB Output is correct
5 Correct 253 ms 10708 KB Output is correct
6 Correct 247 ms 10704 KB Output is correct
7 Correct 182 ms 10716 KB Output is correct
8 Correct 179 ms 10700 KB Output is correct
9 Correct 189 ms 10712 KB Output is correct
10 Correct 269 ms 10720 KB Output is correct
11 Correct 257 ms 10976 KB Output is correct
12 Correct 255 ms 11580 KB Output is correct
13 Correct 185 ms 11196 KB Output is correct
14 Correct 152 ms 11268 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 6452 KB Output is correct
2 Correct 42 ms 7292 KB Output is correct
3 Correct 39 ms 8320 KB Output is correct
4 Correct 125 ms 12764 KB Output is correct
5 Correct 162 ms 12792 KB Output is correct
6 Correct 105 ms 13528 KB Output is correct
7 Correct 196 ms 14160 KB Output is correct
8 Correct 138 ms 13136 KB Output is correct
9 Correct 164 ms 13292 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5508 KB Output is correct
2 Correct 29 ms 6048 KB Output is correct
3 Correct 118 ms 9576 KB Output is correct
4 Correct 213 ms 10708 KB Output is correct
5 Correct 156 ms 10788 KB Output is correct
6 Correct 246 ms 10704 KB Output is correct
7 Correct 191 ms 10716 KB Output is correct
8 Correct 145 ms 10708 KB Output is correct
9 Correct 198 ms 10780 KB Output is correct
10 Correct 150 ms 10704 KB Output is correct
11 Correct 136 ms 11016 KB Output is correct
12 Correct 218 ms 11536 KB Output is correct
13 Correct 161 ms 11344 KB Output is correct
14 Correct 189 ms 11268 KB Output is correct
15 Correct 189 ms 10720 KB Output is correct
16 Correct 165 ms 10720 KB Output is correct
17 Correct 264 ms 11092 KB Output is correct
18 Correct 245 ms 11380 KB Output is correct
19 Correct 226 ms 10764 KB Output is correct
20 Correct 221 ms 11736 KB Output is correct
21 Correct 227 ms 10880 KB Output is correct
22 Correct 141 ms 10860 KB Output is correct
23 Correct 264 ms 10900 KB Output is correct
24 Correct 160 ms 11072 KB Output is correct
25 Correct 259 ms 13836 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 6208 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 6212 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -