Submission #229492

#	Time	Username	Problem	Language	Result	Execution time	Memory
229492		MarcoMeijer	Highway Tolls (IOI18_highway)	C++14	18 / 100	217 ms	21660 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define pb push_back
#define fi first
#define se second
#define sz size()

//===================//
//   begin program   //
//===================//

const int MX = 5e5;
int n, m, a, b;
vi w, u, v;
vi group, visited;
vii adj[MX];
ll dist;

bool sameGroup() {
  RE(i,m) {
    if(group[u[i]] != group[v[i]])  w[i] = 0;
    else                            w[i] = 1;
  }
  dist = ask(w);
  return dist%2;
}
int findSubtree(int edge, int u, int p) {
  vii binS;
  queue<ii> q; q.push({u, p}); binS.pb({edge, u});
  while(!q.empty()) {
    ii p = q.front(); q.pop();
    for(ii v:adj[p.fi]) if(v.fi != p.se) {
      q.push({v.fi, p.fi});
      binS.pb({v.se, v.fi});
    }
  }
  int lb=0, ub=binS.sz-1;
  while(lb != ub) {
    int mid = (lb+ub+1)/2;
    RE(i,n) w[i] = 0;
    REP(i,mid,binS.sz) w[binS[i].fi] = 1;
    if(ask(w) == dist) lb = mid;
    else ub = mid-1;
  }
  return binS[lb].se;
}

void find_pair(int N, vi U, vi V, int A, int B) {
  n=N; a=A; b=B; u=U; v=V;
  m = u.sz;
  w.assign(m, 0);
  RE(i,m) {
    adj[u[i]].pb({v[i], i});
    adj[v[i]].pb({u[i], i});
  }
  if(A == 1 && B == 2) {
    group.resize(n);
    int XOR=0;
    RE(i,17) {
      int bit = (1<<i);
      RE(j,n) group[j] = (j&bit)==0;
      if(sameGroup()) XOR |= bit;
    }
    visited.assign(n, 0);
    RE(i,n) {
      if(visited[i]) continue;
      if((i^XOR) < n) {
        group[i] = 0; group[i^XOR] = 1;
        visited[i] = visited[i^XOR] = 1;
      } else {
        group[i] = 0;
        visited[i] = 1;
      }
    }
    int ones=0;
    RE(i,n) if(group[i]) ones++;
    while(ones != 1) {
      set<int> rem;
      RE(i,n) {
        if(group[i] && rem.sz != ones/2) {
          rem.insert(i);
          group[i] = 0;
        }
      }
      if(!sameGroup()) {
        RE(i,n) group[i] = 0;
        for(int i:rem) group[i] = 1;
      }
      ones=0;
      RE(i,n) if(group[i]) ones++;
    }
    int ans = 0;
    RE(i,n) if(group[i]) ans = i;
    answer(ans, ans^XOR);
    return;
  }
  
  dist = ask(w);
  RE(i,m) w[i] = 1;
  int ones = n;
  while(ones != 1) {
    set<int> rem;
    RE(i,m) if(w[i] && rem.sz < ones/2) {
      w[i] = 0;
      rem.insert(i);
    }
    if(dist == ask(w)) {
      RE(i,n) w[i] = 0;
      for(int i:rem) w[i] = 1;
    }
    ones = 0;
    RE(i,m) if(w[i]) ones++;
  }
  RE(i,m) if(w[i]) {
    answer(findSubtree(i, u[i], v[i]), findSubtree(i, v[i], u[i]));
  }
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, vi, vi, int, int)':
highway.cpp:95:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(group[i] && rem.sz != ones/2) {
                        ~~~~~~~^~~~~~~~~
highway.cpp:118:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     RE(i,m) if(w[i] && rem.sz < ones/2) {
                        ~~~~~~~^~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 18 / 18
• Subtask 6: 0 / 31