oj.uz

Submission #139475

# Submission time Handle Problem Language Result Execution time Memory
139475 2019-07-31T20:29:33 Z CaroLinda Highway Tolls (IOI18_highway) C++14
12 / 100
 210 ms 8948 KB 
#include "highway.h"
#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i=a;i<b;i++)
#define pii pair<int,int>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

const int MAXN = 9e4+ 10 ;
const int MAXM = 13e4+10 ;

using namespace std ;

struct Edge
{

	int j , id ;

	Edge(int j = 0 , int id = 0) 
		: j(j) , id(id) {}

} ;

int n , m , S , T ;

vector<int> toAsk , possible ;

ll oldVal , newVal , rad ;

bool marc[MAXN] ;

vector<Edge> adj[MAXN] ;

int edgePai[MAXN] ;

// --------------------------------

void dfs(int x , ll depth )
{

	if( depth == rad ) possible.pb(x) ;

	marc[x] = true ;

	for(Edge e : adj[x])
		if( !marc[e.j] ) 
		{
			edgePai[e.j] = e.id ;
			dfs(e.j,depth+1) ;
		}

}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  
  m = U.size();
  n = N ;

  lp(i,0,m)
  {

  		
  	int a = U[i] , b = V[i] ;

  	adj[a].pb(Edge(b,i)) ;
  	adj[b].pb(Edge(a,i)) ;

  	toAsk.pb(0) ;

  }

  oldVal = ask(toAsk) ;
  rad = oldVal/A ;

  edgePai[0] = -1 ;
  dfs(0,0) ;

  int l = 0 , r = possible.size() - 1 , mid , best = 0 ;

  while(l<=r)
  {
  		mid = (l+r)/2 ;

  		lp( i, l , mid+1 )
  			toAsk[ edgePai[possible[i]] ] = 1 ;

  		newVal = ask(toAsk) ;

  		lp(i,l,mid+1) 
  			toAsk[ edgePai[possible[i]] ] = 0 ;

  		 if( A < B ? newVal > oldVal : newVal < oldVal ) 
  		 {
  		 	r = mid - 1;
  		 	best = mid ;
  		 }

  		 else l = mid+1 ;

  }

  T = possible[best] ;

  answer(S,T) ;
  

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 KB Output is correct
2 Correct 4 ms 2448 KB Output is correct
3 Correct 5 ms 2452 KB Output is correct
4 Correct 4 ms 2424 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2552 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2348 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 18 ms 2440 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 5 ms 2340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2492 KB Output is correct
2 Correct 22 ms 2988 KB Output is correct
3 Correct 198 ms 8136 KB Output is correct
4 Correct 191 ms 8136 KB Output is correct
5 Correct 210 ms 8136 KB Output is correct
6 Correct 196 ms 8000 KB Output is correct
7 Correct 180 ms 8092 KB Output is correct
8 Correct 184 ms 8140 KB Output is correct
9 Correct 177 ms 8040 KB Output is correct
10 Correct 194 ms 8132 KB Output is correct
11 Correct 147 ms 8456 KB Output is correct
12 Correct 166 ms 8948 KB Output is correct
13 Correct 197 ms 8524 KB Output is correct
14 Correct 142 ms 8184 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
0 / 33.0

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

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 3176 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 21 ms 3252 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -