oj.uz

Submission #103069

# Submission time Handle Problem Language Result Execution time Memory
103069 2019-03-29T01:48:48 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 339 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=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)
{
    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]) 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 21 ms 21368 KB Output is correct
2 Correct 21 ms 21372 KB Output is correct
3 Correct 21 ms 21368 KB Output is correct
4 Correct 21 ms 21392 KB Output is correct
5 Correct 21 ms 21416 KB Output is correct
6 Correct 21 ms 21412 KB Output is correct
7 Correct 21 ms 21380 KB Output is correct
8 Correct 21 ms 21460 KB Output is correct
9 Correct 21 ms 21472 KB Output is correct
10 Correct 21 ms 21460 KB Output is correct
11 Correct 22 ms 21416 KB Output is correct
12 Correct 21 ms 21464 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21532 KB Output is correct
2 Correct 42 ms 22172 KB Output is correct
3 Correct 215 ms 27984 KB Output is correct
4 Correct 243 ms 27984 KB Output is correct
5 Correct 226 ms 27988 KB Output is correct
6 Correct 208 ms 27996 KB Output is correct
7 Correct 224 ms 27972 KB Output is correct
8 Correct 203 ms 27980 KB Output is correct
9 Correct 215 ms 27976 KB Output is correct
10 Correct 200 ms 27976 KB Output is correct
11 Correct 218 ms 27512 KB Output is correct
12 Correct 210 ms 27624 KB Output is correct
13 Correct 210 ms 27360 KB Output is correct
14 Correct 210 ms 27728 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 22184 KB Output is correct
2 Correct 55 ms 22836 KB Output is correct
3 Correct 71 ms 23492 KB Output is correct
4 Correct 188 ms 27328 KB Output is correct
5 Correct 182 ms 27348 KB Output is correct
6 Correct 167 ms 27724 KB Output is correct
7 Correct 177 ms 27412 KB Output is correct
8 Correct 169 ms 27380 KB Output is correct
9 Correct 177 ms 27552 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 22264 KB Output is correct
3 Correct 182 ms 26840 KB Output is correct
4 Correct 210 ms 27960 KB Output is correct
5 Correct 197 ms 27976 KB Output is correct
6 Correct 197 ms 27956 KB Output is correct
7 Correct 203 ms 27976 KB Output is correct
8 Correct 205 ms 27876 KB Output is correct
9 Correct 213 ms 27980 KB Output is correct
10 Correct 209 ms 28016 KB Output is correct
11 Correct 210 ms 27356 KB Output is correct
12 Correct 223 ms 27768 KB Output is correct
13 Correct 222 ms 27984 KB Output is correct
14 Correct 222 ms 27404 KB Output is correct
15 Correct 199 ms 27972 KB Output is correct
16 Correct 204 ms 27968 KB Output is correct
17 Correct 214 ms 27860 KB Output is correct
18 Correct 218 ms 27380 KB Output is correct
19 Correct 212 ms 27972 KB Output is correct
20 Correct 191 ms 27540 KB Output is correct
21 Correct 169 ms 28728 KB Output is correct
22 Correct 173 ms 28724 KB Output is correct
23 Correct 194 ms 28264 KB Output is correct
24 Correct 188 ms 28256 KB Output is correct
25 Correct 215 ms 27928 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22288 KB Output is correct
2 Correct 45 ms 22344 KB Output is correct
3 Correct 237 ms 28624 KB Output is correct
4 Correct 252 ms 29200 KB Output is correct
5 Correct 339 ms 29996 KB Output is correct
6 Incorrect 270 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 48 ms 22228 KB Output is correct
2 Correct 46 ms 22240 KB Output is correct
3 Correct 234 ms 28536 KB Output is correct
4 Incorrect 238 ms 28944 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -