oj.uz

Submission #103105

# Submission time Handle Problem Language Result Execution time Memory
103105 2019-03-29T03:28:06 Z daniel920712 Highway Tolls (IOI18_highway) C++14
100 / 100
 334 ms 30368 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=0;i<=(l+r)/2;i++) how[i]=1;
    if(ask(how)>t)
    {
        for(i=0;i<=(l+r)/2;i++) how[i]=0;
        return F(l,(l+r)/2);

    }
    else
    {
        for(i=0;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-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])
        {
            //printf("%d\n",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 26 ms 21368 KB Output is correct
2 Correct 26 ms 21496 KB Output is correct
3 Correct 22 ms 21496 KB Output is correct
4 Correct 22 ms 21388 KB Output is correct
5 Correct 22 ms 21368 KB Output is correct
6 Correct 22 ms 21496 KB Output is correct
7 Correct 21 ms 21460 KB Output is correct
8 Correct 21 ms 21536 KB Output is correct
9 Correct 21 ms 21464 KB Output is correct
10 Correct 21 ms 21340 KB Output is correct
11 Correct 21 ms 21416 KB Output is correct
12 Correct 21 ms 21460 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21500 KB Output is correct
2 Correct 40 ms 22172 KB Output is correct
3 Correct 195 ms 27972 KB Output is correct
4 Correct 189 ms 28000 KB Output is correct
5 Correct 210 ms 27992 KB Output is correct
6 Correct 204 ms 27976 KB Output is correct
7 Correct 213 ms 28060 KB Output is correct
8 Correct 208 ms 27972 KB Output is correct
9 Correct 194 ms 27980 KB Output is correct
10 Correct 218 ms 27944 KB Output is correct
11 Correct 211 ms 27516 KB Output is correct
12 Correct 229 ms 27656 KB Output is correct
13 Correct 218 ms 27348 KB Output is correct
14 Correct 218 ms 27732 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 22196 KB Output is correct
2 Correct 57 ms 22776 KB Output is correct
3 Correct 72 ms 23540 KB Output is correct
4 Correct 191 ms 27336 KB Output is correct
5 Correct 188 ms 27336 KB Output is correct
6 Correct 193 ms 27780 KB Output is correct
7 Correct 160 ms 27384 KB Output is correct
8 Correct 178 ms 27444 KB Output is correct
9 Correct 195 ms 27620 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21504 KB Output is correct
2 Correct 43 ms 22184 KB Output is correct
3 Correct 178 ms 26792 KB Output is correct
4 Correct 187 ms 27968 KB Output is correct
5 Correct 185 ms 27920 KB Output is correct
6 Correct 207 ms 27972 KB Output is correct
7 Correct 225 ms 27976 KB Output is correct
8 Correct 208 ms 27956 KB Output is correct
9 Correct 224 ms 27996 KB Output is correct
10 Correct 193 ms 28012 KB Output is correct
11 Correct 216 ms 27352 KB Output is correct
12 Correct 219 ms 27848 KB Output is correct
13 Correct 253 ms 27992 KB Output is correct
14 Correct 215 ms 27420 KB Output is correct
15 Correct 197 ms 27976 KB Output is correct
16 Correct 188 ms 27980 KB Output is correct
17 Correct 217 ms 27852 KB Output is correct
18 Correct 199 ms 27380 KB Output is correct
19 Correct 228 ms 27920 KB Output is correct
20 Correct 208 ms 27476 KB Output is correct
21 Correct 187 ms 28708 KB Output is correct
22 Correct 183 ms 28744 KB Output is correct
23 Correct 197 ms 28268 KB Output is correct
24 Correct 183 ms 28236 KB Output is correct
25 Correct 199 ms 27944 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 22228 KB Output is correct
2 Correct 45 ms 22308 KB Output is correct
3 Correct 203 ms 28616 KB Output is correct
4 Correct 236 ms 29192 KB Output is correct
5 Correct 334 ms 30136 KB Output is correct
6 Correct 326 ms 30016 KB Output is correct
7 Correct 299 ms 30084 KB Output is correct
8 Correct 312 ms 30016 KB Output is correct
9 Correct 263 ms 27596 KB Output is correct
10 Correct 255 ms 28212 KB Output is correct
11 Correct 254 ms 28648 KB Output is correct
12 Correct 309 ms 29660 KB Output is correct
13 Correct 296 ms 29828 KB Output is correct
14 Correct 286 ms 30048 KB Output is correct
15 Correct 267 ms 30040 KB Output is correct
16 Correct 281 ms 28616 KB Output is correct
17 Correct 200 ms 28636 KB Output is correct
18 Correct 188 ms 28768 KB Output is correct
19 Correct 192 ms 28540 KB Output is correct
20 Correct 200 ms 28620 KB Output is correct
21 Correct 256 ms 29844 KB Output is correct

Subtask #6
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 22200 KB Output is correct
2 Correct 40 ms 22348 KB Output is correct
3 Correct 265 ms 28516 KB Output is correct
4 Correct 202 ms 28820 KB Output is correct
5 Correct 237 ms 28820 KB Output is correct
6 Correct 292 ms 29972 KB Output is correct
7 Correct 227 ms 28380 KB Output is correct
8 Correct 199 ms 28824 KB Output is correct
9 Correct 220 ms 29088 KB Output is correct
10 Correct 258 ms 30120 KB Output is correct
11 Correct 271 ms 29868 KB Output is correct
12 Correct 322 ms 30024 KB Output is correct
13 Correct 258 ms 28740 KB Output is correct
14 Correct 210 ms 28220 KB Output is correct
15 Correct 218 ms 28648 KB Output is correct
16 Correct 317 ms 28204 KB Output is correct
17 Correct 270 ms 28660 KB Output is correct
18 Correct 302 ms 28156 KB Output is correct
19 Correct 283 ms 29636 KB Output is correct
20 Correct 312 ms 29908 KB Output is correct
21 Correct 290 ms 30040 KB Output is correct
22 Correct 320 ms 30176 KB Output is correct
23 Correct 311 ms 30040 KB Output is correct
24 Correct 324 ms 30052 KB Output is correct
25 Correct 293 ms 30048 KB Output is correct
26 Correct 287 ms 30072 KB Output is correct
27 Correct 191 ms 28768 KB Output is correct
28 Correct 200 ms 28532 KB Output is correct
29 Correct 195 ms 28804 KB Output is correct
30 Correct 180 ms 28640 KB Output is correct
31 Correct 199 ms 28608 KB Output is correct
32 Correct 200 ms 28560 KB Output is correct
33 Correct 197 ms 28756 KB Output is correct
34 Correct 190 ms 28696 KB Output is correct
35 Correct 203 ms 28716 KB Output is correct
36 Correct 183 ms 28536 KB Output is correct
37 Correct 210 ms 28720 KB Output is correct
38 Correct 184 ms 28668 KB Output is correct
39 Correct 283 ms 30368 KB Output is correct
40 Correct 322 ms 30204 KB Output is correct
41 Correct 295 ms 29716 KB Output is correct
42 Correct 312 ms 29812 KB Output is correct