Submission #76679

#	Time	Username	Problem	Language	Result	Execution time	Memory
76679		Xylofo	Highway Tolls (IOI18_highway)	C++14	51 / 100	1334 ms	262148 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i<(int)b; ++i)
using vi = vector<int>;
using ll = long long;

struct off_map {
  map<vi,vi> m;
  vi off;
  off_map(int a) : off(a,0) {}
  void inc(vi& x) {rep(i,0,x.size()) off[i] += x[i];}
  vi get(vi&& y) {
    rep(i,0,y.size()) y[i] -= off[i];
    if(m.count(y)) return m[y];
    else return vi{};
  }
  void ins(vi&& y, vi&& a) {
    rep(i,0,y.size()) y[i] -= off[i];
    vi &x = m[y];
    x.insert(x.end(),a.begin(),a.end());
  }
};
vi match;
vector<pair<int,int> > poss;

void mrg(off_map&a, off_map&b){
  if(a.m.size() < b.m.size()) swap(a.m,b.m), swap(a.off,b.off);
  vector<pair<vi,vi> > to_ins;
  for(auto x:b.m) {
    vi xx = x.first;
    rep(i,0,xx.size()) xx[i] += b.off[i];
    to_ins.emplace_back(xx, x.second);
  }
  for(auto x:to_ins) {
    vi dlt(match.size());
    rep(i,0,dlt.size()) dlt[i] = match[i] - x.first[i];
    vi y = a.get(move(dlt));
    if(!y.empty()) {
      for(int t:y) for(int s:x.second) {
        poss.emplace_back(t,s);
      }
    }
  }
  for(auto x:to_ins) a.ins(move(x.first), move(x.second));
}

void find_pair(int n, vi U, vi V, int A, int B) {
  int m = U.size();
  vector<vector<pair<int,int> > > g(n);
  rep(i,0,m) {
    g[U[i]].emplace_back(V[i],i);
    g[V[i]].emplace_back(U[i],i);
  }
  int X = 60;
  vector<vi> w(X,vi(m));
  rep(i,0,X) {
    rep(j,0,m) w[i][j] = rand()%2;
    ll toll = ask(w[i]);
    match.push_back(toll);
  }
  //rep(i,0,X) cerr << "!!" << match[i] << endl;
  vi vis(n,0);
  function<off_map(int,int)> dfs = [&](int x, int p) {
    //if(vis[x]) exit(0);
    vis[x] = true;
    off_map ds(X);
    ds.ins(vi(X,0), vi{x});
    int UP = -1;
    for(auto y:g[x]) {
      if(y.first != p) {
        off_map s = dfs(y.first, x);
        mrg(ds,s);
      }
      else UP = y.second;
    }
    if(UP != -1) {
      vi up(X);
      rep(i,0,X) up[i] = w[i][UP] ? B : A;
      ds.inc(up);
    }
    return ds;
  };
  dfs(0,-1);
  //cerr << "!" << poss.size() << endl;
  //assert(poss.size() == 1);
  answer(poss[0].first, poss[0].second);
}

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