oj.uz

Submission #823260

# Submission time Handle Problem Language Result Execution time Memory
823260 2023-08-12T10:08:55 Z Trumling Highway Tolls (IOI18_highway) C++14
5 / 100
 193 ms 262144 KB 
#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);
  for(int i=0;i<M;i++)
  {
    g[U[i]].pb({V[i],i});
    g[V[i]].pb({U[i],i});
  }
 dfs(0,0);
 vector<int>a(M,0);

 ll ans=ask(a);
 /*
 vector<int>v;
 for(int i=1;i<N;i++)
 if(d[i]==ans/A)
 {
    v.pb(R[i]);
 }*/
ll st=0;
 for(int i=1;i<N;i++)
    if(d[i]==ans/A)
    {
        a[R[i]]=1;
        ll curr=ask(a);
        if(curr>ans)
        {
            st=i;
            break;
        }
        a[R[i]]=0;
    }
 
/*

 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[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;
    }
    //cout<<l<<' '<<r<<'\n';
 }
 for(int i=1;i<N;i++)
 if(R[i]==v[l])
 {
    ans=i;
    break;
 }
 */
answer(0,st);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 388 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 193 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -