oj.uz

Submission #76679

# Submission time Handle Problem Language Result Execution time Memory
76679 2018-09-15T14:40:17 Z Xylofo Highway Tolls (IOI18_highway) C++14
51 / 100
 1334 ms 262148 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 396 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 432 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 352 KB Output is correct
7 Correct 3 ms 340 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 4 ms 296 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1144 KB Output is correct
2 Correct 120 ms 8660 KB Output is correct
3 Correct 1329 ms 68920 KB Output is correct
4 Correct 1313 ms 74056 KB Output is correct
5 Correct 1317 ms 69868 KB Output is correct
6 Correct 1331 ms 71632 KB Output is correct
7 Correct 1308 ms 74580 KB Output is correct
8 Correct 1334 ms 76220 KB Output is correct
9 Correct 1318 ms 82912 KB Output is correct
10 Correct 1269 ms 66472 KB Output is correct
11 Correct 1055 ms 86864 KB Output is correct
12 Correct 1058 ms 79556 KB Output is correct
13 Correct 1038 ms 89080 KB Output is correct
14 Correct 1257 ms 96588 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 11648 KB Output is correct
2 Correct 141 ms 23084 KB Output is correct
3 Correct 248 ms 34436 KB Output is correct
4 Correct 789 ms 102868 KB Output is correct
5 Correct 777 ms 102872 KB Output is correct
6 Correct 767 ms 102808 KB Output is correct
7 Correct 789 ms 102764 KB Output is correct
8 Correct 817 ms 102856 KB Output is correct
9 Correct 941 ms 102840 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1152 KB Output is correct
2 Correct 117 ms 7892 KB Output is correct
3 Correct 994 ms 53152 KB Output is correct
4 Correct 1291 ms 73484 KB Output is correct
5 Correct 1319 ms 75072 KB Output is correct
6 Correct 1322 ms 76704 KB Output is correct
7 Correct 1322 ms 69556 KB Output is correct
8 Correct 1290 ms 84120 KB Output is correct
9 Correct 1322 ms 72220 KB Output is correct
10 Correct 1316 ms 72520 KB Output is correct
11 Correct 1158 ms 77616 KB Output is correct
12 Correct 1187 ms 86800 KB Output is correct
13 Correct 1147 ms 83428 KB Output is correct
14 Correct 1142 ms 88840 KB Output is correct
15 Correct 1302 ms 78496 KB Output is correct
16 Correct 1308 ms 74892 KB Output is correct
17 Correct 1018 ms 88988 KB Output is correct
18 Correct 1056 ms 81316 KB Output is correct
19 Correct 1306 ms 75028 KB Output is correct
20 Correct 988 ms 78760 KB Output is correct
21 Correct 783 ms 62608 KB Output is correct
22 Correct 802 ms 62624 KB Output is correct
23 Correct 850 ms 72072 KB Output is correct
24 Correct 830 ms 64928 KB Output is correct
25 Correct 931 ms 97292 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 786 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 691 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -