oj.uz

Submission #776335

# Submission time Handle Problem Language Result Execution time Memory
776335 2023-07-07T16:59:55 Z I_Love_EliskaM_ Highway Tolls (IOI18_highway) C++14
69 / 100
 186 ms 17800 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) {
  int shift=0;
  while (!((a^b)&1)) {
  	++shift;
  	a>>=1;
  	b>>=1;
  }
  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);
    x>>=shift;
    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);
    x>>=shift;
    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);
    }
  }
  l=0, r=n-2;
  ll S=ask(vector<int>(m,1))>>shift;
  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);
	x>>=shift;
    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:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     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 2 ms 4944 KB Output is correct
2 Correct 2 ms 4944 KB Output is correct
3 Correct 3 ms 4944 KB Output is correct
4 Correct 2 ms 4944 KB Output is correct
5 Correct 2 ms 4944 KB Output is correct
6 Correct 2 ms 5012 KB Output is correct
7 Correct 2 ms 4944 KB Output is correct
8 Correct 2 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 2 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 11 ms 5664 KB Output is correct
3 Correct 116 ms 11328 KB Output is correct
4 Correct 86 ms 11316 KB Output is correct
5 Correct 95 ms 11292 KB Output is correct
6 Correct 80 ms 11328 KB Output is correct
7 Correct 100 ms 11328 KB Output is correct
8 Correct 120 ms 11324 KB Output is correct
9 Correct 95 ms 11332 KB Output is correct
10 Correct 119 ms 11316 KB Output is correct
11 Correct 131 ms 13044 KB Output is correct
12 Correct 130 ms 13624 KB Output is correct
13 Correct 120 ms 13300 KB Output is correct
14 Correct 116 ms 12788 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6352 KB Output is correct
2 Correct 16 ms 7872 KB Output is correct
3 Correct 26 ms 9180 KB Output is correct
4 Correct 75 ms 17784 KB Output is correct
5 Correct 80 ms 17728 KB Output is correct
6 Correct 105 ms 17720 KB Output is correct
7 Correct 64 ms 17716 KB Output is correct
8 Correct 121 ms 17768 KB Output is correct
9 Correct 88 ms 17800 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5072 KB Output is correct
2 Correct 13 ms 5592 KB Output is correct
3 Correct 66 ms 10028 KB Output is correct
4 Correct 111 ms 11256 KB Output is correct
5 Correct 117 ms 11308 KB Output is correct
6 Correct 85 ms 11236 KB Output is correct
7 Correct 72 ms 11284 KB Output is correct
8 Correct 95 ms 11244 KB Output is correct
9 Correct 111 ms 11320 KB Output is correct
10 Correct 114 ms 11328 KB Output is correct
11 Correct 87 ms 12184 KB Output is correct
12 Correct 87 ms 13320 KB Output is correct
13 Correct 101 ms 12916 KB Output is correct
14 Correct 85 ms 13256 KB Output is correct
15 Correct 71 ms 11320 KB Output is correct
16 Correct 122 ms 11204 KB Output is correct
17 Correct 103 ms 12648 KB Output is correct
18 Correct 113 ms 12920 KB Output is correct
19 Correct 76 ms 11264 KB Output is correct
20 Correct 77 ms 13748 KB Output is correct
21 Correct 73 ms 11508 KB Output is correct
22 Correct 98 ms 11520 KB Output is correct
23 Correct 69 ms 11504 KB Output is correct
24 Correct 106 ms 12084 KB Output is correct
25 Correct 101 ms 17080 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6184 KB Output is correct
2 Correct 12 ms 6148 KB Output is correct
3 Correct 113 ms 15348 KB Output is correct
4 Correct 116 ms 15940 KB Output is correct
5 Correct 165 ms 17176 KB Output is correct
6 Correct 143 ms 17200 KB Output is correct
7 Correct 186 ms 17188 KB Output is correct
8 Correct 142 ms 17200 KB Output is correct
9 Correct 117 ms 13928 KB Output is correct
10 Correct 123 ms 14216 KB Output is correct
11 Correct 100 ms 15020 KB Output is correct
12 Correct 115 ms 16280 KB Output is correct
13 Correct 178 ms 16764 KB Output is correct
14 Correct 157 ms 17188 KB Output is correct
15 Correct 147 ms 17224 KB Output is correct
16 Correct 105 ms 15060 KB Output is correct
17 Correct 81 ms 15300 KB Output is correct
18 Correct 116 ms 15504 KB Output is correct
19 Correct 123 ms 15444 KB Output is correct
20 Correct 79 ms 15524 KB Output is correct
21 Correct 138 ms 17188 KB Output is correct

Subtask #6
0 / 31.0

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