oj.uz

Submission #102979

# Submission time Handle Problem Language Result Execution time Memory
102979 2019-03-28T10:20:48 Z daniel920712 Highway Tolls (IOI18_highway) C++14
0 / 100
 23 ms 3324 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <utility>
#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 F(int l,int r)
{
    //printf("%d %d\n",l,r);
    //printf("%d %d\n",l,r);
    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 -1;
        else return F((l+r)/2+1,r);
    }
}
void Find1(int here)
{
    for(auto i:road[here])
    {
        if(!have_V[i.first])
        {
            a.push_back(make_pair(i.second,i.first));
            have_V[i.first]=1;
            Find1(i.second);
        }

    }
}
void Find2(int here)
{
    for(auto i:road[here])
    {
        if(!have_V[i.first])
        {
            b.push_back(make_pair(i.second,i.first));
            have_V[i.first]=1;
            Find2(i.second);
        }

    }
}

int Ans1(int l,int r)
{
    int i;
    for(i=l;i<=(l+r)/2;i++) how[a[i].first]=1;
    if(ask(how)>t)
    {
        for(i=0;i<=(l+r)/2;i++) how[a[i].first]=0;
        if(l==r) return a[l].second;
        else return Ans1(l,(l+r)/2);

    }
    else
    {
        for(i=l;i<=(l+r)/2;i++) how[a[i].first]=0;
        if(l==r) return -1;
        else return Ans1((l+r)/2+1,r);
    }
}

int Ans2(int l,int r)
{
    int i;
    for(i=l;i<=(l+r)/2;i++) how[b[i].first]=1;
    if(ask(how)>t)
    {
        for(i=0;i<=(l+r)/2;i++) how[b[i].first]=0;
        if(l==r) return b[l].second;
        else return Ans2(l,(l+r)/2);

    }
    else
    {
        for(i=l;i<=(l+r)/2;i++) how[b[i].first]=0;
        if(l==r) return -1;
        else 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;
    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;
    Find1(U[edge]);
    Find2(V[edge]);
    a.push_back(make_pair(edge,U[edge]));
    b.push_back(make_pair(edge,V[edge]));
    //a.push_back(V[edge]);
    x=Ans1(0,a.size()-1);
    y=Ans2(0,b.size()-1);
    answer(x,y);
    //printf("%d\n",edge);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Incorrect 4 ms 2424 KB Output is incorrect: {s, t} is wrong.
3 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

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

Subtask #6
0 / 31.0

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