oj.uz

Submission #776331

# Submission time Handle Problem Language Result Execution time Memory
776331 2023-07-07T16:55:27 Z I_Love_EliskaM_ Highway Tolls (IOI18_highway) C++14
51 / 100
 138 ms 16240 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const ll inf = 1e18;
#define pi pair<int,int>
#define f first
#define s second

const int maxn=1e5;
vector<pi> adj[maxn];
pi e[maxn];
vector<int> z;
void dfs(int u, int p) {
  for(auto&ed:adj[u]) {
    int v=ed.f, i=ed.s;
    if (v==p) continue;
    e[i]={u,v};
    z.pb(i);
    dfs(v,u);
  }
}


mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void find(int n, vector<int>u, vector<int>v, int a, int b) {
  if (a!=1 || b!=2) exit(0);
  int m=u.size();
  vector<int> f,s;
  ll x;
  forn(it,18) {
    f.clear(), s.clear();
    vector<int> ok(n);
    forn(i,n) ok[i]=rng()&1;
    forn(i,n) (ok[i]?f:s).pb(i);
    if (min(f.size(),s.size())==0) {
      --it; continue;
    }
    vector<int> q(m,0);
    forn(i,m) q[i]=ok[u[i]]==ok[v[i]];
    x = ask(q);
    if (x&1) {
      break;
    }
  }
  if (!(x&1)) exit(0);
  if (f.size()>s.size());
  assert(f.size());
  int l=0, r=f.size()-1;
  while (l<r) {
    int mid=(l+r)>>1;
    vector<int> ok(n);
    for(auto&x:s) ok[x]=1;
    forn(i,mid+1) ok[f[i]]=1;
    vector<int> q(m,0);
    forn(i,m) q[i]=ok[u[i]]==ok[v[i]];
    x = ask(q);
    if (x&1) l=mid+1;
    else r=mid;
  }
  int st = f[r];
  vector<vector<pi>> g(n);
  forn(i,m) {
    g[u[i]].pb({v[i],i});
    g[v[i]].pb({u[i],i});
  }
  vector<int> vis(n); vis[st]=1;
  queue<int> q; q.push(st);
  while (q.size()) {
    auto u=q.front();q.pop();
    for(auto&ed:g[u]) {
      int v=ed.f, i=ed.s;
      if (vis[v]) continue;
      vis[v]=1;
      e[i]={u,v};
      q.push(v);
      z.pb(i);
    }
  }
  if (z.size()!=(n-1)) exit(1);
  l=0, r=n-2;
  ll S=ask(vector<int>(m,1));
  while (l<r) {
    int mid=(l+r)>>1;
    vector<int> q(m,1);
    for(int i=mid+1;i<z.size();++i) q[z[i]]=0;
    ll x=ask(q);
    if (x==S) r=mid;
    else l=mid+1;
  }
  answer(st,e[z[r]].s);

}

void find_pair(int n, vector<int>u, vector<int>v, int a, int b) {
  int m=u.size();
  if (m!=n-1) {
    find(n,u,v,a,b);
    return;
  }
  forn(i,n-1) adj[u[i]].pb({v[i],i}), adj[v[i]].pb({u[i],i});
  int k=0; forn(i,n) if (adj[i].size()==1) k=i;
  dfs(k,-1);

  ll s = ask(vector<int>(m,1));

  int l=0, r=n-2;
  while (l<r) {
    int m=(l+r)>>1;
    vector<int> q(n-1);
    forn(i,m+1) q[z[i]]=1;
    ll x=ask(q);
    if (x==s) r=m;
    else l=m+1;
  }

  k = e[z[r]].s;
  //k=0;
  z.clear();
  dfs(k,-1);

  l=0, r=n-2;
  while (l<r) {
    int m=(l+r)>>1;
    vector<int> q(n-1);
    forn(i,m+1) q[z[i]]=1;
    ll x=ask(q);
    if (x==s) r=m;
    else l=m+1;
  }
  answer(k,e[z[r]].s);

}

Compilation message

highway.cpp: In function 'void find(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:84:15: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |   if (z.size()!=(n-1)) exit(1);
      |       ~~~~~~~~^~~~~~~
highway.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=mid+1;i<z.size();++i) q[z[i]]=0;
      |                     ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2616 KB Output is correct
2 Correct 6 ms 3248 KB Output is correct
3 Correct 124 ms 8984 KB Output is correct
4 Correct 132 ms 8976 KB Output is correct
5 Correct 76 ms 8976 KB Output is correct
6 Correct 88 ms 8912 KB Output is correct
7 Correct 107 ms 8976 KB Output is correct
8 Correct 100 ms 8976 KB Output is correct
9 Correct 111 ms 8976 KB Output is correct
10 Correct 99 ms 8904 KB Output is correct
11 Correct 119 ms 10644 KB Output is correct
12 Correct 115 ms 11404 KB Output is correct
13 Correct 125 ms 11008 KB Output is correct
14 Correct 88 ms 10512 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 4048 KB Output is correct
2 Correct 22 ms 5504 KB Output is correct
3 Correct 21 ms 6892 KB Output is correct
4 Correct 63 ms 15452 KB Output is correct
5 Correct 63 ms 15384 KB Output is correct
6 Correct 96 ms 15352 KB Output is correct
7 Correct 68 ms 15580 KB Output is correct
8 Correct 82 ms 15400 KB Output is correct
9 Correct 92 ms 15372 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2640 KB Output is correct
2 Correct 9 ms 3356 KB Output is correct
3 Correct 61 ms 7520 KB Output is correct
4 Correct 92 ms 8980 KB Output is correct
5 Correct 71 ms 8976 KB Output is correct
6 Correct 86 ms 9096 KB Output is correct
7 Correct 92 ms 8976 KB Output is correct
8 Correct 91 ms 8920 KB Output is correct
9 Correct 113 ms 8976 KB Output is correct
10 Correct 119 ms 8988 KB Output is correct
11 Correct 93 ms 9892 KB Output is correct
12 Correct 95 ms 10996 KB Output is correct
13 Correct 89 ms 10572 KB Output is correct
14 Correct 126 ms 10944 KB Output is correct
15 Correct 103 ms 8908 KB Output is correct
16 Correct 118 ms 8984 KB Output is correct
17 Correct 95 ms 10244 KB Output is correct
18 Correct 99 ms 10620 KB Output is correct
19 Correct 90 ms 8984 KB Output is correct
20 Correct 83 ms 11476 KB Output is correct
21 Correct 84 ms 9172 KB Output is correct
22 Correct 91 ms 9172 KB Output is correct
23 Correct 84 ms 9156 KB Output is correct
24 Correct 72 ms 9752 KB Output is correct
25 Correct 97 ms 14692 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3760 KB Output is correct
2 Correct 13 ms 3792 KB Output is correct
3 Correct 107 ms 13188 KB Output is correct
4 Runtime error 138 ms 16240 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 2896 KB Output is incorrect: answered not exactly once.
2 Halted 0 ms 0 KB -