oj.uz

Submission #103099

# Submission time Handle Problem Language Result Execution time Memory
103099 2019-03-29T03:16:02 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 310 ms 30000 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[900005];
int n,m,x=-1,y=-1;
long long t;
bool have_V[900005]={0};
bool have_E[1300005]={0};
int F(int l,int 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=l;i<=(l+r)/2;i++) how[i]=0;
        return F(l,(l+r)/2);

    }
    else
    {
        for(i=l;i<=(l+r)/2;i++) how[i]=0;
        return F((l+r)/2+1,r);
    }
}
int Ans1(int l,int 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<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;
    have_E[edge]=1;
    a.push_back(make_pair(edge,U[edge]));
    b.push_back(make_pair(edge,V[edge]));

    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])
        {
            //printf("%d\n",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 20 ms 21464 KB Output is correct
2 Correct 20 ms 21468 KB Output is correct
3 Correct 20 ms 21460 KB Output is correct
4 Correct 21 ms 21368 KB Output is correct
5 Correct 22 ms 21464 KB Output is correct
6 Correct 21 ms 21464 KB Output is correct
7 Correct 20 ms 21464 KB Output is correct
8 Correct 21 ms 21368 KB Output is correct
9 Correct 20 ms 21368 KB Output is correct
10 Correct 21 ms 21416 KB Output is correct
11 Correct 22 ms 21416 KB Output is correct
12 Correct 22 ms 21496 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21600 KB Output is correct
2 Correct 40 ms 22264 KB Output is correct
3 Correct 213 ms 27976 KB Output is correct
4 Correct 208 ms 28016 KB Output is correct
5 Correct 205 ms 27972 KB Output is correct
6 Correct 206 ms 27968 KB Output is correct
7 Correct 222 ms 27980 KB Output is correct
8 Correct 211 ms 27968 KB Output is correct
9 Correct 200 ms 27972 KB Output is correct
10 Correct 213 ms 27980 KB Output is correct
11 Correct 183 ms 27508 KB Output is correct
12 Correct 211 ms 27640 KB Output is correct
13 Correct 210 ms 27384 KB Output is correct
14 Correct 216 ms 27784 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 22188 KB Output is correct
2 Correct 54 ms 22748 KB Output is correct
3 Correct 74 ms 23452 KB Output is correct
4 Correct 163 ms 27372 KB Output is correct
5 Correct 193 ms 27312 KB Output is correct
6 Correct 152 ms 27716 KB Output is correct
7 Correct 181 ms 27392 KB Output is correct
8 Correct 147 ms 27388 KB Output is correct
9 Correct 186 ms 27672 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21636 KB Output is correct
2 Correct 41 ms 22136 KB Output is correct
3 Correct 149 ms 26844 KB Output is correct
4 Correct 212 ms 27968 KB Output is correct
5 Correct 213 ms 27884 KB Output is correct
6 Correct 186 ms 27956 KB Output is correct
7 Correct 193 ms 27980 KB Output is correct
8 Correct 198 ms 27936 KB Output is correct
9 Correct 217 ms 28004 KB Output is correct
10 Correct 204 ms 28024 KB Output is correct
11 Correct 202 ms 27352 KB Output is correct
12 Correct 218 ms 27848 KB Output is correct
13 Correct 227 ms 27980 KB Output is correct
14 Correct 209 ms 27404 KB Output is correct
15 Correct 209 ms 27976 KB Output is correct
16 Correct 200 ms 27972 KB Output is correct
17 Correct 214 ms 27848 KB Output is correct
18 Correct 204 ms 27472 KB Output is correct
19 Correct 199 ms 27956 KB Output is correct
20 Correct 206 ms 27460 KB Output is correct
21 Correct 151 ms 28724 KB Output is correct
22 Correct 155 ms 28800 KB Output is correct
23 Correct 197 ms 28272 KB Output is correct
24 Correct 163 ms 28240 KB Output is correct
25 Correct 231 ms 27940 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 22220 KB Output is correct
2 Correct 33 ms 22240 KB Output is correct
3 Correct 210 ms 28616 KB Output is correct
4 Correct 264 ms 29248 KB Output is correct
5 Correct 310 ms 29992 KB Output is correct
6 Incorrect 278 ms 30000 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 37 ms 22184 KB Output is correct
2 Correct 48 ms 22396 KB Output is correct
3 Correct 232 ms 28552 KB Output is correct
4 Incorrect 211 ms 28840 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -