Submission #100274

#	Time	Username	Problem	Language	Result	Execution time	Memory
100274		tugushka	Highway Tolls (IOI18_highway)	C++14	Compilation error	0 ms	0 KiB

highway

#include<bits/stdc++.h>
#include "highway.h"
#define mp make_pair
#define pb push_back
using namespace std;

using pii = pair < int, int >;

vector < vector < pii > > to;
vector < pii > edg, ans;
vector<int> w;
int n, m, A, B;
long long L;

void bfs( int start){
  bool a[N+1];
  memset( a, 0, sizeof(a) );
  ans.clear();
  queue < int > q;
  q.push( start );
  used[start] = 1;

  while( !q.empty() ){
    int sz = q.size();
    while(sz--){
      int u = q.front();
      q.pop();
      for( int v : to[u] ){
        if( used[v.first] ) continue;
        q.push( v.first );
        used[v.first] = 1;
        ans.push_back( mp( v.second, v.first ) );
      }
    }
  }
}

int findEnd( int start, int startParent ){
  bfs( start, startParent );

  fill( w.begin(), w.end(), 0 );
  L = ask( w );

  /*
    	cerr << "############\n";
    	cerr << "start : "<< start << ' ' << startParent << endl;
    	for(int i = 0 ; i < ans.size() ; i++){
    		cerr << ans[i].second << ' ' << ans[i].first << endl;
    	}*/

  if( ans.empty() ) return start;

  // cerr << L << endl;

  long long now;
  int l = 0, r = ans.size()-1;
  while( l+1 < r ){
    int mid = (l+r)>>1;

    fill( w.begin(), w.end(), 0 );
    for(int i = mid ; i <= r ; i++){
      w[ans[i].first] = 1;
    }

    now = ask( w );

    // cerr << l << ' ' << r << " : " << mid << ' ' << now << endl;

    if( now > L ) l = mid;
    else r = mid-1;
  }

  // cerr << l << ' ' << r << endl;

  if( l != r ){
    fill( w.begin(), w.end(), 0 );
    w[ ans[l+1].first ] = 1;
    now = ask( w );
    if( now > L ) return ans[l+1].second;

    fill( w.begin(), w.end(), 0 );
    w[ ans[l].first ] = 1;
    now = ask( w );
    if( now > L ) return ans[l].second;

    return start;
  }

  fill( w.begin(), w.end(), 0 );
  w[ ans[l].first ] = 1;
  now = ask( w );
  if( now > L ) return ans[l].second;

  return start;
}

int findEdge( int start ){
  bfs( start, -1 );

  fill( w.begin(), w.end(), 0 );
  L = ask( w );

  long long now;
  int l = 0, r = ans.size()-1;
  while( l+1 < r ){
    int mid = (l+r)>>1;

    fill( w.begin(), w.end(), 0 );
    for(int i = mid ; i <= r ; i++){
      w[ans[i].first] = 1;
    }

    now = ask( w );

    // cerr << l << ' ' << r << " : " << mid << ' ' << now << endl;

    if( now > L ) l = mid;
    else r = mid-1;
  }

  if( l != r ){
    fill( w.begin(), w.end(), 0 );
    w[ ans[l].first ] = 1;
    now = ask( w );
    if( now > L ) return ans[l].first;

    fill( w.begin(), w.end(), 0 );
    w[ ans[l+1].first ] = 1;
    now = ask( w );
    if( now > L ) return ans[l+1].first;

    return start;
  }

  return ans[l].first;
}

void find_pair(int N, vector<int> U, vector<int> V, int _A, int _B) {
  n = N; A = _A; B = _B; m = U.size();
  w.resize(m);
  to.resize(n+1);

  for(int i = 0 ; i < m ; i++){
    to[ U[i] ].pb( mp( V[i], i ) );
    to[ V[i] ].pb( mp( U[i], i ) );
    edg.push_back( mp( V[i], U[i] ) );
  }

  int e = findEdge( 0 );
  // cerr << "### " << edg[e].first << ' ' << edg[e].second << endl;

  int s = findEnd( edg[e].first, edg[e].second );
  int t = findEnd( edg[e].second, edg[e].first );

  // cerr << "## " << s << ' ' << t << endl;

  answer( s, t );
}
/*
    4 3 1 3 1 3
    0 1
    0 2
    0 3

    10 9 1 5 3 9
    0 1
    0 2
    2 9
    1 3
    1 4
    1 5
    3 6
    4 7
    4 8

    */

Compilation message (stderr)

highway.cpp: In function 'void bfs(int)':
highway.cpp:16:10: error: 'N' was not declared in this scope
   bool a[N+1];
          ^
highway.cpp:17:11: error: 'a' was not declared in this scope
   memset( a, 0, sizeof(a) );
           ^
highway.cpp:21:3: error: 'used' was not declared in this scope
   used[start] = 1;
   ^~~~
highway.cpp:28:24: error: cannot convert 'std::pair<int, int>' to 'int' in initialization
       for( int v : to[u] ){
                        ^
highway.cpp:29:20: error: request for member 'first' in 'v', which is of non-class type 'int'
         if( used[v.first] ) continue;
                    ^~~~~
highway.cpp:30:19: error: request for member 'first' in 'v', which is of non-class type 'int'
         q.push( v.first );
                   ^~~~~
highway.cpp:31:16: error: request for member 'first' in 'v', which is of non-class type 'int'
         used[v.first] = 1;
                ^~~~~
highway.cpp:32:30: error: request for member 'second' in 'v', which is of non-class type 'int'
         ans.push_back( mp( v.second, v.first ) );
                              ^~~~~~
highway.cpp:32:40: error: request for member 'first' in 'v', which is of non-class type 'int'
         ans.push_back( mp( v.second, v.first ) );
                                        ^~~~~
highway.cpp: In function 'int findEnd(int, int)':
highway.cpp:39:27: error: too many arguments to function 'void bfs(int)'
   bfs( start, startParent );
                           ^
highway.cpp:15:6: note: declared here
 void bfs( int start){
      ^~~
highway.cpp: In function 'int findEdge(int)':
highway.cpp:98:18: error: too many arguments to function 'void bfs(int)'
   bfs( start, -1 );
                  ^
highway.cpp:15:6: note: declared here
 void bfs( int start){
      ^~~