oj.uz

Submission #103070

# Submission time Handle Problem Language Result Execution time Memory
103070 2019-03-29T01:53:31 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 293 ms 30004 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;
        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)
{
    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 21472 KB Output is correct
2 Correct 21 ms 21464 KB Output is correct
3 Correct 20 ms 21464 KB Output is correct
4 Correct 21 ms 21472 KB Output is correct
5 Correct 21 ms 21368 KB Output is correct
6 Correct 21 ms 21548 KB Output is correct
7 Correct 21 ms 21468 KB Output is correct
8 Correct 21 ms 21368 KB Output is correct
9 Correct 21 ms 21568 KB Output is correct
10 Correct 22 ms 21460 KB Output is correct
11 Correct 21 ms 21368 KB Output is correct
12 Correct 21 ms 21468 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21496 KB Output is correct
2 Correct 37 ms 22256 KB Output is correct
3 Correct 214 ms 27964 KB Output is correct
4 Correct 208 ms 27976 KB Output is correct
5 Correct 217 ms 27960 KB Output is correct
6 Correct 206 ms 27972 KB Output is correct
7 Correct 208 ms 27976 KB Output is correct
8 Correct 219 ms 27972 KB Output is correct
9 Correct 180 ms 27976 KB Output is correct
10 Correct 209 ms 27980 KB Output is correct
11 Correct 216 ms 27516 KB Output is correct
12 Correct 233 ms 27632 KB Output is correct
13 Correct 204 ms 27352 KB Output is correct
14 Correct 229 ms 27820 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 22084 KB Output is correct
2 Correct 54 ms 22744 KB Output is correct
3 Correct 71 ms 23480 KB Output is correct
4 Correct 187 ms 27428 KB Output is correct
5 Correct 175 ms 27344 KB Output is correct
6 Correct 196 ms 27728 KB Output is correct
7 Correct 157 ms 27364 KB Output is correct
8 Correct 167 ms 27372 KB Output is correct
9 Correct 184 ms 27564 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21496 KB Output is correct
2 Correct 41 ms 22164 KB Output is correct
3 Correct 153 ms 26836 KB Output is correct
4 Correct 203 ms 27940 KB Output is correct
5 Correct 216 ms 27972 KB Output is correct
6 Correct 210 ms 27952 KB Output is correct
7 Correct 202 ms 27984 KB Output is correct
8 Correct 210 ms 27952 KB Output is correct
9 Correct 224 ms 27980 KB Output is correct
10 Correct 209 ms 28016 KB Output is correct
11 Correct 215 ms 27340 KB Output is correct
12 Correct 226 ms 27732 KB Output is correct
13 Correct 212 ms 27984 KB Output is correct
14 Correct 208 ms 27400 KB Output is correct
15 Correct 209 ms 28004 KB Output is correct
16 Correct 187 ms 27984 KB Output is correct
17 Correct 224 ms 27860 KB Output is correct
18 Correct 197 ms 27372 KB Output is correct
19 Correct 191 ms 28032 KB Output is correct
20 Correct 196 ms 27464 KB Output is correct
21 Correct 177 ms 28800 KB Output is correct
22 Correct 178 ms 28716 KB Output is correct
23 Correct 192 ms 28268 KB Output is correct
24 Correct 196 ms 28360 KB Output is correct
25 Correct 219 ms 27944 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 22224 KB Output is correct
2 Correct 46 ms 22324 KB Output is correct
3 Correct 240 ms 28612 KB Output is correct
4 Correct 260 ms 29192 KB Output is correct
5 Correct 293 ms 29988 KB Output is correct
6 Incorrect 282 ms 30004 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 43 ms 22232 KB Output is correct
2 Correct 42 ms 22376 KB Output is correct
3 Correct 232 ms 28540 KB Output is correct
4 Incorrect 256 ms 28832 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -