oj.uz

Submission #103103

# Submission time Handle Problem Language Result Execution time Memory
103103 2019-03-29T03:27:21 Z daniel920712 Highway Tolls (IOI18_highway) C++14
51 / 100
 327 ms 30180 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=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-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 21 ms 21368 KB Output is correct
2 Correct 20 ms 21460 KB Output is correct
3 Correct 25 ms 21368 KB Output is correct
4 Correct 22 ms 21472 KB Output is correct
5 Correct 27 ms 21368 KB Output is correct
6 Correct 21 ms 21420 KB Output is correct
7 Correct 22 ms 21416 KB Output is correct
8 Correct 21 ms 21436 KB Output is correct
9 Correct 21 ms 21576 KB Output is correct
10 Correct 21 ms 21464 KB Output is correct
11 Correct 21 ms 21368 KB Output is correct
12 Correct 21 ms 21372 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 21544 KB Output is correct
2 Correct 34 ms 22172 KB Output is correct
3 Correct 209 ms 27988 KB Output is correct
4 Correct 206 ms 27984 KB Output is correct
5 Correct 204 ms 27980 KB Output is correct
6 Correct 197 ms 27956 KB Output is correct
7 Correct 205 ms 27980 KB Output is correct
8 Correct 230 ms 27980 KB Output is correct
9 Correct 205 ms 27980 KB Output is correct
10 Correct 211 ms 27980 KB Output is correct
11 Correct 183 ms 27588 KB Output is correct
12 Correct 210 ms 27552 KB Output is correct
13 Correct 212 ms 27356 KB Output is correct
14 Correct 215 ms 27740 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 22100 KB Output is correct
2 Correct 50 ms 22764 KB Output is correct
3 Correct 64 ms 23520 KB Output is correct
4 Correct 146 ms 27412 KB Output is correct
5 Correct 140 ms 27360 KB Output is correct
6 Correct 146 ms 27720 KB Output is correct
7 Correct 172 ms 27308 KB Output is correct
8 Correct 164 ms 27380 KB Output is correct
9 Correct 182 ms 27544 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 21624 KB Output is correct
2 Correct 28 ms 22328 KB Output is correct
3 Correct 142 ms 26832 KB Output is correct
4 Correct 209 ms 27988 KB Output is correct
5 Correct 196 ms 27904 KB Output is correct
6 Correct 177 ms 27956 KB Output is correct
7 Correct 174 ms 27976 KB Output is correct
8 Correct 211 ms 27936 KB Output is correct
9 Correct 180 ms 27988 KB Output is correct
10 Correct 247 ms 28020 KB Output is correct
11 Correct 215 ms 27352 KB Output is correct
12 Correct 197 ms 27724 KB Output is correct
13 Correct 217 ms 27988 KB Output is correct
14 Correct 213 ms 27496 KB Output is correct
15 Correct 159 ms 28024 KB Output is correct
16 Correct 207 ms 27984 KB Output is correct
17 Correct 216 ms 27860 KB Output is correct
18 Correct 210 ms 27416 KB Output is correct
19 Correct 209 ms 28032 KB Output is correct
20 Correct 210 ms 27448 KB Output is correct
21 Correct 193 ms 28720 KB Output is correct
22 Correct 163 ms 28736 KB Output is correct
23 Correct 175 ms 28280 KB Output is correct
24 Correct 218 ms 28248 KB Output is correct
25 Correct 229 ms 27944 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22204 KB Output is correct
2 Correct 41 ms 22312 KB Output is correct
3 Correct 241 ms 28612 KB Output is correct
4 Correct 271 ms 29212 KB Output is correct
5 Correct 301 ms 30136 KB Output is correct
6 Correct 307 ms 30020 KB Output is correct
7 Correct 318 ms 29984 KB Output is correct
8 Correct 323 ms 29996 KB Output is correct
9 Correct 255 ms 27656 KB Output is correct
10 Correct 266 ms 28224 KB Output is correct
11 Correct 248 ms 28700 KB Output is correct
12 Correct 313 ms 29660 KB Output is correct
13 Correct 322 ms 29800 KB Output is correct
14 Correct 301 ms 30052 KB Output is correct
15 Correct 307 ms 30036 KB Output is correct
16 Correct 280 ms 28616 KB Output is correct
17 Correct 192 ms 28636 KB Output is correct
18 Incorrect 197 ms 28784 KB Output is incorrect: {s, t} is wrong.
19 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 22336 KB Output is correct
2 Correct 45 ms 22236 KB Output is correct
3 Correct 223 ms 28532 KB Output is correct
4 Correct 244 ms 28824 KB Output is correct
5 Correct 270 ms 28784 KB Output is correct
6 Correct 298 ms 29976 KB Output is correct
7 Correct 229 ms 28384 KB Output is correct
8 Correct 261 ms 28820 KB Output is correct
9 Correct 289 ms 29112 KB Output is correct
10 Correct 300 ms 30120 KB Output is correct
11 Correct 298 ms 29840 KB Output is correct
12 Correct 293 ms 30036 KB Output is correct
13 Correct 296 ms 28648 KB Output is correct
14 Correct 275 ms 28144 KB Output is correct
15 Correct 286 ms 28648 KB Output is correct
16 Correct 249 ms 28280 KB Output is correct
17 Correct 286 ms 28628 KB Output is correct
18 Correct 236 ms 28276 KB Output is correct
19 Correct 310 ms 29744 KB Output is correct
20 Correct 325 ms 30000 KB Output is correct
21 Correct 297 ms 30016 KB Output is correct
22 Correct 299 ms 30156 KB Output is correct
23 Correct 315 ms 30056 KB Output is correct
24 Correct 327 ms 30052 KB Output is correct
25 Correct 323 ms 30180 KB Output is correct
26 Correct 308 ms 30048 KB Output is correct
27 Incorrect 201 ms 28764 KB Output is incorrect: {s, t} is wrong.
28 Halted 0 ms 0 KB -