oj.uz

Submission #776332

# Submission time Handle Problem Language Result Execution time Memory
776332 2023-07-07T16:56:44 Z I_Love_EliskaM_ Highway Tolls (IOI18_highway) C++14
69 / 100
 170 ms 17804 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=2e5;
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 3 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 2 ms 4944 KB Output is correct
4 Correct 3 ms 4944 KB Output is correct
5 Correct 3 ms 4944 KB Output is correct
6 Correct 3 ms 4944 KB Output is correct
7 Correct 3 ms 4944 KB Output is correct
8 Correct 3 ms 4944 KB Output is correct
9 Correct 2 ms 4944 KB Output is correct
10 Correct 2 ms 4944 KB Output is correct
11 Correct 2 ms 4944 KB Output is correct
12 Correct 3 ms 4944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 9 ms 5720 KB Output is correct
3 Correct 99 ms 11320 KB Output is correct
4 Correct 116 ms 11332 KB Output is correct
5 Correct 114 ms 11328 KB Output is correct
6 Correct 103 ms 11276 KB Output is correct
7 Correct 97 ms 11324 KB Output is correct
8 Correct 124 ms 11308 KB Output is correct
9 Correct 108 ms 11320 KB Output is correct
10 Correct 102 ms 11324 KB Output is correct
11 Correct 118 ms 13012 KB Output is correct
12 Correct 113 ms 13624 KB Output is correct
13 Correct 122 ms 13344 KB Output is correct
14 Correct 86 ms 12920 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6352 KB Output is correct
2 Correct 16 ms 7836 KB Output is correct
3 Correct 36 ms 9236 KB Output is correct
4 Correct 81 ms 17724 KB Output is correct
5 Correct 95 ms 17716 KB Output is correct
6 Correct 73 ms 17724 KB Output is correct
7 Correct 82 ms 17724 KB Output is correct
8 Correct 67 ms 17804 KB Output is correct
9 Correct 96 ms 17796 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5072 KB Output is correct
2 Correct 15 ms 5708 KB Output is correct
3 Correct 67 ms 9964 KB Output is correct
4 Correct 93 ms 11316 KB Output is correct
5 Correct 105 ms 11324 KB Output is correct
6 Correct 119 ms 11320 KB Output is correct
7 Correct 95 ms 11328 KB Output is correct
8 Correct 85 ms 11208 KB Output is correct
9 Correct 120 ms 11244 KB Output is correct
10 Correct 88 ms 11248 KB Output is correct
11 Correct 120 ms 12192 KB Output is correct
12 Correct 114 ms 13328 KB Output is correct
13 Correct 116 ms 12872 KB Output is correct
14 Correct 122 ms 13244 KB Output is correct
15 Correct 71 ms 11204 KB Output is correct
16 Correct 104 ms 11324 KB Output is correct
17 Correct 88 ms 12476 KB Output is correct
18 Correct 92 ms 13004 KB Output is correct
19 Correct 98 ms 11260 KB Output is correct
20 Correct 81 ms 13816 KB Output is correct
21 Correct 89 ms 11516 KB Output is correct
22 Correct 100 ms 11576 KB Output is correct
23 Correct 97 ms 11536 KB Output is correct
24 Correct 101 ms 12076 KB Output is correct
25 Correct 133 ms 17080 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 6144 KB Output is correct
2 Correct 18 ms 6216 KB Output is correct
3 Correct 110 ms 15444 KB Output is correct
4 Correct 145 ms 15940 KB Output is correct
5 Correct 157 ms 17208 KB Output is correct
6 Correct 144 ms 17192 KB Output is correct
7 Correct 170 ms 17184 KB Output is correct
8 Correct 126 ms 17184 KB Output is correct
9 Correct 118 ms 13748 KB Output is correct
10 Correct 97 ms 14252 KB Output is correct
11 Correct 124 ms 15004 KB Output is correct
12 Correct 117 ms 16296 KB Output is correct
13 Correct 127 ms 16752 KB Output is correct
14 Correct 147 ms 17196 KB Output is correct
15 Correct 152 ms 17168 KB Output is correct
16 Correct 163 ms 15068 KB Output is correct
17 Correct 110 ms 15304 KB Output is correct
18 Correct 144 ms 15496 KB Output is correct
19 Correct 102 ms 15436 KB Output is correct
20 Correct 101 ms 15528 KB Output is correct
21 Correct 150 ms 17172 KB Output is correct

Subtask #6
0 / 31.0

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