oj.uz

Submission #102987

# Submission time Handle Problem Language Result Execution time Memory
102987 2019-03-28T10:53:52 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 209 ms 13228 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <utility>
#include "highway.h"
using namespace std;
vector < int > how;
vector < pair < int , int > > a,b;
vector < pair < int , int > > road[90005];
int n,m,x=-1,y=-1;
long long t;
bool have_V[90005]={0};

int F(int l,int r)
{
    //printf("%d %d\n",l,r);
    //printf("%d %d\n",l,r);
    int i;
    for(i=l;i<=(l+r)/2;i++) how[i]=1;
    if(ask(how)>t)
    {
        for(i=0;i<=(l+r)/2;i++) how[i]=0;
        if(l==r) return l;
        else return F(l,(l+r)/2);

    }
    else
    {
        for(i=l;i<=(l+r)/2;i++) how[i]=0;
        if(l==r) return -1;
        else return F((l+r)/2+1,r);
    }
}
void Find1(int here)
{
    //printf("a:%d\n",here);
    for(auto i:road[here])
    {
        if(!have_V[i.first])
        {
            a.push_back(make_pair(i.second,i.first));
            have_V[i.first]=1;
            Find1(i.first);
        }

    }
}
void Find2(int here)
{
    //printf("b:%d\n",here);
    for(auto i:road[here])
    {
        if(!have_V[i.first])
        {
            b.push_back(make_pair(i.second,i.first));
            have_V[i.first]=1;
            Find2(i.first);
        }

    }
}

int Ans1(int l,int r)
{
    //printf("a:%d %d\n",l,r);
    int i;
    if(l==r) return a[l].second;
    for(i=(l+r)/2+1;i<=r;i++) how[a[i].first]=1;
    if(ask(how)==t)
    {
        for(i=(l+r)/2+1;i<=r;i++) how[a[i].first]=0;
        return Ans1(l,(l+r)/2);
    }
    else
    {
        for(i=(l+r)/2+1;i<=r;i++) how[a[i].first]=0;
        return Ans1((l+r)/2+1,r);
    }
}

int Ans2(int l,int r)
{
    int i;
    if(l==r) return b[l].second;
    for(i=(l+r)/2+1;i<=r;i++) how[b[i].first]=1;
    if(ask(how)==t)
    {
        for(i=(l+r)/2+1;i<=r;i++) how[b[i].first]=0;
        return Ans2(l,(l+r)/2);
    }
    else
    {
        for(i=(l+r)/2+1;i<=r;i++) how[b[i].first]=0;
        return Ans2((l+r)/2+1,r);
    }
}


void find_pair(int N,vector < int > U,vector < int > V,int A,int B)
{
    int i,edge;
    n=N;
    m=U.size();
    for(i=0;i<m;i++) how.push_back(0);
    for(i=0;i<m;i++)
    {
        road[U[i]].push_back(make_pair(V[i],i));
        road[V[i]].push_back(make_pair(U[i],i));
    }
    t=ask(how);
    edge=F(0,m-1);
    have_V[U[edge]]=1;
    have_V[V[edge]]=1;
    a.push_back(make_pair(edge,U[edge]));
    b.push_back(make_pair(edge,V[edge]));
    //x=U[edge];
    //y=v[edge];
    Find1(U[edge]);
    Find2(V[edge]);

    /*printf("a");
    for(auto i:a) printf("%d ",i.first);
    printf("\n");*/

    /*printf("b");
    for(auto i:b) printf("%d ",i.first);
    printf("\n");*/

    x=Ans1(0,a.size()-1);
    y=Ans2(0,b.size()-1);
    answer(x,y);
    //printf("%d %d %d\n",edge,U[edge],V[edge]);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 24 ms 3320 KB Output is correct
3 Correct 171 ms 8744 KB Output is correct
4 Correct 190 ms 8756 KB Output is correct
5 Correct 184 ms 8732 KB Output is correct
6 Correct 185 ms 8732 KB Output is correct
7 Correct 180 ms 8772 KB Output is correct
8 Correct 202 ms 8736 KB Output is correct
9 Correct 184 ms 8736 KB Output is correct
10 Correct 197 ms 8748 KB Output is correct
11 Correct 201 ms 9332 KB Output is correct
12 Correct 188 ms 9984 KB Output is correct
13 Correct 187 ms 9636 KB Output is correct
14 Correct 194 ms 9712 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3712 KB Output is correct
2 Correct 33 ms 4748 KB Output is correct
3 Correct 53 ms 5904 KB Output is correct
4 Correct 177 ms 11428 KB Output is correct
5 Correct 162 ms 11492 KB Output is correct
6 Correct 152 ms 12856 KB Output is correct
7 Correct 167 ms 13228 KB Output is correct
8 Correct 158 ms 12408 KB Output is correct
9 Correct 176 ms 12320 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2488 KB Output is correct
2 Correct 21 ms 3148 KB Output is correct
3 Correct 153 ms 7612 KB Output is correct
4 Correct 182 ms 8728 KB Output is correct
5 Correct 168 ms 8744 KB Output is correct
6 Correct 188 ms 8756 KB Output is correct
7 Correct 171 ms 8752 KB Output is correct
8 Correct 189 ms 8744 KB Output is correct
9 Correct 150 ms 8744 KB Output is correct
10 Correct 194 ms 8728 KB Output is correct
11 Correct 209 ms 9340 KB Output is correct
12 Correct 190 ms 10496 KB Output is correct
13 Correct 195 ms 9856 KB Output is correct
14 Correct 175 ms 9568 KB Output is correct
15 Correct 186 ms 8728 KB Output is correct
16 Correct 184 ms 8740 KB Output is correct
17 Correct 168 ms 9468 KB Output is correct
18 Correct 200 ms 9848 KB Output is correct
19 Correct 180 ms 8756 KB Output is correct
20 Correct 176 ms 10440 KB Output is correct
21 Correct 184 ms 9280 KB Output is correct
22 Correct 169 ms 9272 KB Output is correct
23 Correct 147 ms 8888 KB Output is correct
24 Correct 182 ms 9272 KB Output is correct
25 Correct 197 ms 12868 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 3304 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 27 ms 3296 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -