oj.uz

Submission #103052

# Submission time Handle Problem Language Result Execution time Memory
103052 2019-03-29T00:43:29 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 222 ms 13660 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 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)
{
    //printf("a:%d\n",here);
    for(auto i:road[here])
    {
        if(!have_V[i.first]&&have_E[i.second])
        {
            a.push_back(make_pair(i.second,i.first));
            have_V[i.first]=1;
            Find1(i.first);
        }

    }
}
void Find2(int here)
{
    //printf("b:%d\n",here);
    for(auto i:road[here])
    {
        if(!have_V[i.first]&&have_E[i.second])
        {
            b.push_back(make_pair(i.second,i.first));
            have_V[i.first]=1;
            Find2(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];
    for(i=0;i<m;i++)
    {
        if(Find(U[i])!=Find(V[i]))
        {
            have_E[i]=1;
            father[Find(U[i])]=Find(V[i]);

        }
    }
    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]);

    /*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 2344 KB Output is correct
2 Correct 4 ms 2440 KB Output is correct
3 Correct 4 ms 2440 KB Output is correct
4 Correct 4 ms 2524 KB Output is correct
5 Correct 4 ms 2504 KB Output is correct
6 Correct 4 ms 2448 KB Output is correct
7 Correct 4 ms 2524 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2444 KB Output is correct
10 Correct 4 ms 2444 KB Output is correct
11 Correct 4 ms 2520 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 2504 KB Output is correct
2 Correct 42 ms 3184 KB Output is correct
3 Correct 197 ms 9188 KB Output is correct
4 Correct 196 ms 9212 KB Output is correct
5 Correct 205 ms 9192 KB Output is correct
6 Correct 197 ms 9212 KB Output is correct
7 Correct 222 ms 9368 KB Output is correct
8 Correct 203 ms 9224 KB Output is correct
9 Correct 209 ms 9308 KB Output is correct
10 Correct 194 ms 9224 KB Output is correct
11 Correct 215 ms 9824 KB Output is correct
12 Correct 209 ms 10368 KB Output is correct
13 Correct 171 ms 10116 KB Output is correct
14 Correct 214 ms 10204 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3816 KB Output is correct
2 Correct 42 ms 4824 KB Output is correct
3 Correct 57 ms 6144 KB Output is correct
4 Correct 159 ms 11972 KB Output is correct
5 Correct 170 ms 11936 KB Output is correct
6 Correct 172 ms 13288 KB Output is correct
7 Correct 164 ms 13660 KB Output is correct
8 Correct 164 ms 12756 KB Output is correct
9 Correct 169 ms 12756 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 45 ms 3224 KB Output is correct
3 Correct 147 ms 7964 KB Output is correct
4 Correct 173 ms 9224 KB Output is correct
5 Correct 196 ms 9220 KB Output is correct
6 Correct 196 ms 9216 KB Output is correct
7 Correct 174 ms 9300 KB Output is correct
8 Correct 169 ms 9256 KB Output is correct
9 Correct 208 ms 9216 KB Output is correct
10 Correct 200 ms 9252 KB Output is correct
11 Correct 172 ms 9824 KB Output is correct
12 Correct 214 ms 10980 KB Output is correct
13 Correct 207 ms 10212 KB Output is correct
14 Correct 208 ms 10028 KB Output is correct
15 Correct 200 ms 9200 KB Output is correct
16 Correct 189 ms 9220 KB Output is correct
17 Correct 212 ms 9956 KB Output is correct
18 Correct 204 ms 10336 KB Output is correct
19 Correct 200 ms 9224 KB Output is correct
20 Correct 199 ms 11028 KB Output is correct
21 Correct 183 ms 9768 KB Output is correct
22 Correct 167 ms 10276 KB Output is correct
23 Correct 173 ms 9484 KB Output is correct
24 Correct 187 ms 9628 KB Output is correct
25 Correct 201 ms 13300 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 3212 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 -