oj.uz

Submission #103058

# Submission time Handle Problem Language Result Execution time Memory
103058 2019-03-29T00:59:37 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 227 ms 9888 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[90005];
int n,m,x=-1,y=-1;
long long t;
bool have_V[90005]={0};
bool have_E[130005]={0};
int father[90005];
int Find(int here)
{
    if(father[here]==here) return here;
    father[here]=Find(father[here]);
    return father[here];
}
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)
{
    queue < int > temp;
    temp.push(here);
    while(!temp.empty())
    {
        here=temp.front();
        temp.pop();
        for(auto i:road[here])
        {
            if(!have_V[i.first])
            {
                a.push_back(make_pair(i.second,i.first));
                have_V[i.first]=1;
                have_E[i.second]=1;
                temp.push(i.first);
            }

        }
    }

}
void Find2(int here)
{
    queue < int > temp;
    temp.push(here);
    while(!temp.empty())
    {
        here=temp.front();
        temp.pop();
        for(auto i:road[here])
        {
            if(!have_V[i.first])
            {
                b.push_back(make_pair(i.second,i.first));
                have_V[i.first]=1;
                have_E[i.second]=1;
                temp.push(i.first);
            }

        }
    }

}

int Ans1(int l,int r)
{
    //printf("a:%d %d\n",l,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;
    n=N;
    m=U.size();
    for(i=0;i<n;i++) father[i]=i;
    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;
    father[U[edge]]=V[edge];
    a.push_back(make_pair(edge,U[edge]));
    b.push_back(make_pair(edge,V[edge]));
    //x=U[edge];
    //y=v[edge];
    Find1(U[edge]);
    Find2(V[edge]);
    for(i=0;i<m;i++) if(!have_E[i]) how[i]=1;
    /*printf("a");
    for(auto i:a) printf("%d ",i.first);
    printf("\n");*/

    /*printf("b");
    for(auto i:b) printf("%d ",i.first);
    printf("\n");*/

    x=Ans1(0,a.size()-1);
    y=Ans2(0,b.size()-1);
    answer(x,y);
    //printf("%d %d %d\n",edge,U[edge],V[edge]);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2444 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2440 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2520 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 21 ms 3320 KB Output is correct
3 Correct 186 ms 9260 KB Output is correct
4 Correct 182 ms 9260 KB Output is correct
5 Correct 185 ms 9268 KB Output is correct
6 Correct 191 ms 9264 KB Output is correct
7 Correct 192 ms 9268 KB Output is correct
8 Correct 205 ms 9260 KB Output is correct
9 Correct 177 ms 9280 KB Output is correct
10 Correct 182 ms 9256 KB Output is correct
11 Correct 198 ms 8664 KB Output is correct
12 Correct 189 ms 8664 KB Output is correct
13 Correct 205 ms 8712 KB Output is correct
14 Correct 208 ms 8656 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3192 KB Output is correct
2 Correct 34 ms 3804 KB Output is correct
3 Correct 53 ms 4480 KB Output is correct
4 Correct 178 ms 8548 KB Output is correct
5 Correct 181 ms 8548 KB Output is correct
6 Correct 168 ms 9176 KB Output is correct
7 Correct 178 ms 8588 KB Output is correct
8 Correct 151 ms 8800 KB Output is correct
9 Correct 155 ms 8628 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2580 KB Output is correct
2 Correct 34 ms 3148 KB Output is correct
3 Correct 142 ms 8056 KB Output is correct
4 Correct 186 ms 9260 KB Output is correct
5 Correct 178 ms 9296 KB Output is correct
6 Correct 187 ms 9292 KB Output is correct
7 Correct 193 ms 9228 KB Output is correct
8 Correct 204 ms 9232 KB Output is correct
9 Correct 178 ms 9256 KB Output is correct
10 Correct 156 ms 9276 KB Output is correct
11 Correct 200 ms 8672 KB Output is correct
12 Correct 186 ms 9188 KB Output is correct
13 Correct 227 ms 8680 KB Output is correct
14 Correct 193 ms 8520 KB Output is correct
15 Correct 174 ms 9272 KB Output is correct
16 Correct 197 ms 9264 KB Output is correct
17 Correct 196 ms 8680 KB Output is correct
18 Correct 186 ms 8668 KB Output is correct
19 Correct 193 ms 9308 KB Output is correct
20 Correct 182 ms 8736 KB Output is correct
21 Correct 149 ms 9888 KB Output is correct
22 Correct 161 ms 9888 KB Output is correct
23 Correct 163 ms 9496 KB Output is correct
24 Correct 181 ms 9316 KB Output is correct
25 Correct 220 ms 8756 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3240 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 27 ms 3320 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -