Submission #823323

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
823323	2023-08-12T10:44:20 Z	Trumling	Highway Tolls (IOI18_highway)	C++14	6 / 100	105 ms	4928 KB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace  std;
#define F first 
#define S second 
#define all(x) x.begin(),x.end()  
typedef long long ll;
#define INF 99999999999999
#define pb  push_back

vector<vector<pair<int,int> > >g;
vector<int>d,R;


void dfs(int start,int pre)
{
    for(pair<int,int> x:g[start])
        if(x.F!=pre)
        {
            d[x.F]=d[start]+1;
            R[x.F]=x.S;
            dfs(x.F,start);
        }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  int M = U.size();
  g.assign(N,vector<pair<int,int> >());
  d.assign(N,0);
  R.assign(N,0);


vector<int>a(M,0);
ll ans=ask(a);

vector<int>v;

for(int i=ans/A/2;i<M;i+=ans/A)
v.pb(i);

 ll l=0,r=v.size()-1;
 ll idx=0;
//cout<<'\n';
 
 while(l<r)
 {
    
    ll  mid=(l+r)/2;
    for(int  i=l;i<=mid;i++)
    a[v[i]]=(idx+1)%2;
 
    ll curr=ask(a);
    if(idx==0)
    {
        if(curr>ans)
        {
           r=mid; 
           idx=1;
        }
        else
        l=mid+1;
    }
    else
    {
        if(curr==ans)
        {
            r=mid;
            idx=0;
        }
        else
        l=mid+1;
    }
 }
 a.assign(M,0);
 ll m=v[l];
 l=m;
 r=M-1;

 while(l<r)
 {
   // cout<<l<<' '<<r<<'\n';
    ll mid=(l+r)/2;

    a[mid]=1;
    ll curr=ask(a);

    if(curr>ans)
    l=mid+1;
    else
    r=mid;

    a[mid]=0;
 }
 
 answer(l,l-ans/A);

}

/*
6 5 1 2 
0 4
0 1  
1 2
2 3
3 4
4 5*/

Subtask #1
0 / 5.0

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

Subtask #2
0 / 7.0

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

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	916 KB	Output is correct
2	Correct	11 ms	1208 KB	Output is correct
3	Correct	32 ms	1816 KB	Output is correct
4	Correct	43 ms	4832 KB	Output is correct
5	Correct	84 ms	4928 KB	Output is correct
6	Correct	47 ms	4752 KB	Output is correct
7	Correct	105 ms	4924 KB	Output is correct
8	Correct	84 ms	4760 KB	Output is correct
9	Correct	44 ms	4764 KB	Output is correct