oj.uz

Submission #103073

# Submission time Handle Problem Language Result Execution time Memory
103073 2019-03-29T02:09:28 Z daniel920712 Highway Tolls (IOI18_highway) C++14
6 / 100
 309 ms 55732 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);
    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());
    y=Ans2(0,b.size());
    answer(x,y);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 21496 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 43308 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 22100 KB Output is correct
2 Correct 51 ms 22844 KB Output is correct
3 Correct 68 ms 23452 KB Output is correct
4 Correct 183 ms 27336 KB Output is correct
5 Correct 165 ms 27344 KB Output is correct
6 Correct 182 ms 27872 KB Output is correct
7 Correct 176 ms 27352 KB Output is correct
8 Correct 173 ms 27392 KB Output is correct
9 Correct 167 ms 27604 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21496 KB Output is correct
2 Correct 42 ms 22240 KB Output is correct
3 Correct 147 ms 26836 KB Output is correct
4 Correct 192 ms 27968 KB Output is correct
5 Correct 206 ms 27964 KB Output is correct
6 Runtime error 273 ms 55732 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22232 KB Output is correct
2 Correct 38 ms 22456 KB Output is correct
3 Correct 229 ms 28620 KB Output is correct
4 Correct 269 ms 29184 KB Output is correct
5 Correct 309 ms 30000 KB Output is correct
6 Incorrect 296 ms 30256 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 41 ms 22312 KB Output is correct
2 Correct 48 ms 22240 KB Output is correct
3 Correct 201 ms 28576 KB Output is correct
4 Incorrect 258 ms 28852 KB Output is incorrect: {s, t} is wrong.
5 Halted 0 ms 0 KB -