oj.uz

Submission #776319

# Submission time Handle Problem Language Result Execution time Memory
776319 2023-07-07T16:17:58 Z I_Love_EliskaM_ Highway Tolls (IOI18_highway) C++14
51 / 100
 133 ms 15444 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);
    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 m=(l+r)>>1;
    vector<int> ok(n);
    for(auto&x:s) ok[x]=1;
    forn(i,m+1) ok[f[i]]=1;
    vector<int> q(m);
    forn(i,m) q[i]=ok[u[i]]==ok[v[i]];
    x = ask(q);
  }
  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 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(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);
  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 2 ms 2640 KB Output is correct
2 Correct 2 ms 2640 KB Output is correct
3 Correct 2 ms 2640 KB Output is correct
4 Correct 1 ms 2640 KB Output is correct
5 Correct 1 ms 2640 KB Output is correct
6 Correct 2 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 3280 KB Output is correct
3 Correct 96 ms 8876 KB Output is correct
4 Correct 111 ms 8976 KB Output is correct
5 Correct 80 ms 8912 KB Output is correct
6 Correct 101 ms 8916 KB Output is correct
7 Correct 91 ms 8980 KB Output is correct
8 Correct 102 ms 8916 KB Output is correct
9 Correct 100 ms 8984 KB Output is correct
10 Correct 98 ms 8980 KB Output is correct
11 Correct 105 ms 10636 KB Output is correct
12 Correct 110 ms 11344 KB Output is correct
13 Correct 103 ms 10928 KB Output is correct
14 Correct 125 ms 10448 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 4016 KB Output is correct
2 Correct 14 ms 5456 KB Output is correct
3 Correct 26 ms 6888 KB Output is correct
4 Correct 83 ms 15436 KB Output is correct
5 Correct 82 ms 15444 KB Output is correct
6 Correct 79 ms 15376 KB Output is correct
7 Correct 102 ms 15376 KB Output is correct
8 Correct 105 ms 15368 KB Output is correct
9 Correct 101 ms 15436 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 8 ms 3380 KB Output is correct
3 Correct 70 ms 7512 KB Output is correct
4 Correct 93 ms 8908 KB Output is correct
5 Correct 82 ms 8912 KB Output is correct
6 Correct 110 ms 8860 KB Output is correct
7 Correct 68 ms 9028 KB Output is correct
8 Correct 110 ms 8900 KB Output is correct
9 Correct 111 ms 8976 KB Output is correct
10 Correct 76 ms 8988 KB Output is correct
11 Correct 133 ms 9832 KB Output is correct
12 Correct 109 ms 10976 KB Output is correct
13 Correct 132 ms 10572 KB Output is correct
14 Correct 113 ms 10960 KB Output is correct
15 Correct 105 ms 9040 KB Output is correct
16 Correct 75 ms 8980 KB Output is correct
17 Correct 93 ms 10192 KB Output is correct
18 Correct 91 ms 10584 KB Output is correct
19 Correct 97 ms 8920 KB Output is correct
20 Correct 109 ms 11396 KB Output is correct
21 Correct 82 ms 9164 KB Output is correct
22 Correct 73 ms 9168 KB Output is correct
23 Correct 78 ms 9148 KB Output is correct
24 Correct 107 ms 9860 KB Output is correct
25 Correct 97 ms 14736 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 2976 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

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