oj.uz

Submission #132731

# Submission time Handle Problem Language Result Execution time Memory
132731 2019-07-19T12:01:17 Z dvdg6566 Highway Tolls (IOI18_highway) C++14
0 / 100
 36 ms 5576 KB 
#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
#define mp make_pair
#define pb emplace_back
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound

vpi V[100100];
int sub[100100];
vi q;
pi par[100100];
int rt;
int ind;
vi top;

void dfs(int x, int p){
	top.pb(x);
	for (auto v:V[x])if (v.f!=p){
		par[v.f] = mp(x, v.s);
		dfs(v.f,x);
	}
}


void find_pair(int N, std::vector<int> U, std::vector<int> _V, int A, int B) {
  int M = U.size();
  assert(M+1==N);
  q.resize(N-1,0);
  for (int i=0;i<M;++i){
  	int a=_V[i];
  	int b=U[i];
  	V[a].pb(b,i);
  	V[b].pb(a,i);
  }
  ll len=ask(q);
  dfs(0,-1);
  for (auto i : top){
  	for(int j=0;j<N-1;++j)q[i]=0;
  	int x=i;
  	while(x){
  		q[par[x].s]=1;
  		x=par[x].f;
  	}
  	// for (int i=0;i<N-1;++i)cout<<q[i]<<' ';cout<<'\n';
  	ll l = ask(q);
  	// cout<<l<<' '<<len<<'\n';
  	if ((ll)len*(ll)B == (ll)l*(ll)A){
  		answer(0,i);
  		return;
  	}
  }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2676 KB Output is correct
2 Correct 4 ms 2760 KB Output is correct
3 Runtime error 8 ms 5364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2724 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3832 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2724 KB Output is incorrect: more than 100 calls to ask.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 5564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 5576 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -