oj.uz

Submission #103060

# Submission time Handle Problem Language Result Execution time Memory
103060 2019-03-29T01:14:16 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 297 ms 11328 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <utility>
#include <queue>
#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};
bool have_E[130005]={0};
int father[90005];
int F(int l,int r)
{
    //printf("%d %d\n",l,r);
    //printf("%d %d\n",l,r);
    if(l==r) return l;
    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 l;
        else return F((l+r)/2+1,r);
    }
}
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,here,x;
    n=N;
    m=U.size();
    for(i=0;i<n;i++) father[i]=i;
    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);
    //printf("%d\n",edge);
    have_V[U[edge]]=1;
    have_V[V[edge]]=1;
    have_E[edge]=1;
    a.push_back(make_pair(edge,U[edge]));
    b.push_back(make_pair(edge,V[edge]));
    //Find1(U[edge]);queue < int > temp;

    queue < pair < int , int > > temp;
    temp.push(make_pair(U[edge],0));
    temp.push(make_pair(V[edge],1));
    while(!temp.empty())
    {
        here=temp.front().first;
        x=temp.front().second;
        temp.pop();
        for(auto i:road[here])
        {
            if(!have_V[i.first])
            {
                //
                have_V[i.first]=1;
                have_E[i.second]=1;
                temp.push(make_pair(i.first,x));
                if(x) b.push_back(make_pair(i.second,i.first));
                else a.push_back(make_pair(i.second,i.first));
            }

        }
    }


    for(i=0;i<m;i++) if(!have_E[i]) how[i]=1;
    x=Ans1(0,a.size()-1);
    y=Ans2(0,b.size()-1);
    answer(x,y);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 19 ms 3316 KB Output is correct
3 Correct 194 ms 9300 KB Output is correct
4 Correct 203 ms 9316 KB Output is correct
5 Correct 187 ms 9296 KB Output is correct
6 Correct 190 ms 9288 KB Output is correct
7 Correct 194 ms 9300 KB Output is correct
8 Correct 207 ms 9304 KB Output is correct
9 Correct 199 ms 9300 KB Output is correct
10 Correct 185 ms 9288 KB Output is correct
11 Correct 201 ms 8844 KB Output is correct
12 Correct 196 ms 8960 KB Output is correct
13 Correct 193 ms 8684 KB Output is correct
14 Correct 203 ms 9132 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3192 KB Output is correct
2 Correct 34 ms 3864 KB Output is correct
3 Correct 57 ms 4588 KB Output is correct
4 Correct 154 ms 8676 KB Output is correct
5 Correct 158 ms 8700 KB Output is correct
6 Correct 164 ms 9064 KB Output is correct
7 Correct 172 ms 8680 KB Output is correct
8 Correct 165 ms 8708 KB Output is correct
9 Correct 164 ms 8960 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2424 KB Output is correct
2 Correct 15 ms 3184 KB Output is correct
3 Correct 138 ms 8096 KB Output is correct
4 Correct 189 ms 9284 KB Output is correct
5 Correct 195 ms 9324 KB Output is correct
6 Correct 178 ms 9332 KB Output is correct
7 Correct 197 ms 9308 KB Output is correct
8 Correct 188 ms 9292 KB Output is correct
9 Correct 206 ms 9312 KB Output is correct
10 Correct 180 ms 9340 KB Output is correct
11 Correct 201 ms 8688 KB Output is correct
12 Correct 196 ms 9056 KB Output is correct
13 Correct 201 ms 9260 KB Output is correct
14 Correct 205 ms 8740 KB Output is correct
15 Correct 205 ms 9360 KB Output is correct
16 Correct 173 ms 9340 KB Output is correct
17 Correct 175 ms 9188 KB Output is correct
18 Correct 197 ms 8688 KB Output is correct
19 Correct 197 ms 9340 KB Output is correct
20 Correct 185 ms 8784 KB Output is correct
21 Correct 148 ms 10044 KB Output is correct
22 Correct 148 ms 10004 KB Output is correct
23 Correct 180 ms 9592 KB Output is correct
24 Correct 153 ms 9568 KB Output is correct
25 Correct 204 ms 9288 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3112 KB Output is correct
2 Correct 29 ms 3320 KB Output is correct
3 Correct 228 ms 9944 KB Output is correct
4 Correct 270 ms 10508 KB Output is correct
5 Correct 297 ms 11328 KB Output is correct
6 Incorrect 277 ms 11328 KB Output is incorrect: {s, t} is wrong.
7 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 3192 KB Output is correct
2 Correct 28 ms 3284 KB Output is correct
3 Correct 237 ms 9992 KB Output is correct
4 Incorrect 232 ms 10164 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -