oj.uz

Submission #776323

# Submission time Handle Problem Language Result Execution time Memory
776323 2023-07-07T16:30:12 Z I_Love_EliskaM_ Highway Tolls (IOI18_highway) C++14
51 / 100
 127 ms 15464 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());
  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> p(n);
  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;
      p[v]=i;
      e[i]={u,v};
      q.push(v);
      adj[u].pb({v,i});
    }
  }
  z.clear();
  dfs(st,-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);
    forn(i,mid+1) q[z[i]]=1;
    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);

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2640 KB Output is correct
2 Correct 2 ms 2688 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 3 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 2 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 2640 KB Output is correct
2 Correct 9 ms 3356 KB Output is correct
3 Correct 106 ms 8980 KB Output is correct
4 Correct 81 ms 8912 KB Output is correct
5 Correct 96 ms 8952 KB Output is correct
6 Correct 107 ms 8940 KB Output is correct
7 Correct 121 ms 8984 KB Output is correct
8 Correct 85 ms 8980 KB Output is correct
9 Correct 127 ms 8980 KB Output is correct
10 Correct 110 ms 8984 KB Output is correct
11 Correct 121 ms 10636 KB Output is correct
12 Correct 103 ms 11284 KB Output is correct
13 Correct 115 ms 10904 KB Output is correct
14 Correct 106 ms 10516 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4016 KB Output is correct
2 Correct 23 ms 5448 KB Output is correct
3 Correct 30 ms 6888 KB Output is correct
4 Correct 64 ms 15464 KB Output is correct
5 Correct 77 ms 15380 KB Output is correct
6 Correct 74 ms 15376 KB Output is correct
7 Correct 77 ms 15380 KB Output is correct
8 Correct 107 ms 15440 KB Output is correct
9 Correct 82 ms 15388 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 13 ms 3376 KB Output is correct
3 Correct 83 ms 7548 KB Output is correct
4 Correct 80 ms 8980 KB Output is correct
5 Correct 90 ms 8936 KB Output is correct
6 Correct 78 ms 8976 KB Output is correct
7 Correct 102 ms 8980 KB Output is correct
8 Correct 114 ms 8908 KB Output is correct
9 Correct 116 ms 8976 KB Output is correct
10 Correct 91 ms 8980 KB Output is correct
11 Correct 118 ms 9832 KB Output is correct
12 Correct 103 ms 10984 KB Output is correct
13 Correct 90 ms 10532 KB Output is correct
14 Correct 88 ms 10956 KB Output is correct
15 Correct 70 ms 8980 KB Output is correct
16 Correct 80 ms 9168 KB Output is correct
17 Correct 122 ms 10128 KB Output is correct
18 Correct 90 ms 10576 KB Output is correct
19 Correct 94 ms 9032 KB Output is correct
20 Correct 95 ms 11404 KB Output is correct
21 Correct 85 ms 9168 KB Output is correct
22 Correct 82 ms 9164 KB Output is correct
23 Correct 92 ms 9148 KB Output is correct
24 Correct 95 ms 9736 KB Output is correct
25 Correct 98 ms 14668 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 4048 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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