oj.uz

Submission #139537

# Submission time Handle Problem Language Result Execution time Memory
139537 2019-08-01T01:22:58 Z CaroLinda Highway Tolls (IOI18_highway) C++14
12 / 100
 201 ms 10464 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 ;

int edgePai[MAXN] ;

vector<int> toAsk , possible ;

ll rad , Prev ;

vector<Edge> adj[MAXN] ;

bool marc[MAXN] ;

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


void prepareDfs()
{
	memset(marc,false, sizeof marc) ;
	possible.resize(0) ;
}

void dfs(int x , ll depth , ll curRad , bool allowed[])
{

	if( depth == curRad ) possible.pb(x) ;
	marc[x] = true ;

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

}


int findSpecial(int s , bool allowed[] , ll curRad ) 
{

	prepareDfs() ;	
	dfs(s , 0 , curRad , allowed) ;

	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 ;

		ll newTot = ask(toAsk) ;

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

		if( newTot > Prev ) 
		{
			r = mid - 1 ;
			best = mid ;
		}

		else l = mid+1 ;

	}

	return possible[best] ;


}

bool allowed[MAXM] ;

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) ;
  	allowed[i] = 1 ;

  }

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

  T = findSpecial(0 , allowed , rad) ;

  answer(S,T) ;

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2428 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2472 KB Output is correct
5 Correct 9 ms 2448 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2444 KB Output is correct
8 Correct 5 ms 2424 KB Output is correct
9 Correct 13 ms 2472 KB Output is correct
10 Correct 5 ms 2444 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 5 ms 2496 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2500 KB Output is correct
2 Correct 21 ms 3064 KB Output is correct
3 Correct 127 ms 8228 KB Output is correct
4 Correct 197 ms 8224 KB Output is correct
5 Correct 198 ms 8260 KB Output is correct
6 Correct 185 ms 8276 KB Output is correct
7 Correct 172 ms 8180 KB Output is correct
8 Correct 138 ms 8220 KB Output is correct
9 Correct 201 ms 8200 KB Output is correct
10 Correct 158 ms 8224 KB Output is correct
11 Correct 146 ms 9564 KB Output is correct
12 Correct 198 ms 10464 KB Output is correct
13 Correct 148 ms 9672 KB Output is correct
14 Correct 144 ms 8944 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 20 ms 4008 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 2552 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 24 ms 3316 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 3284 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -