oj.uz

Submission #139781

# Submission time Handle Problem Language Result Execution time Memory
139781 2019-08-01T11:36:20 Z CaroLinda Highway Tolls (IOI18_highway) C++14
51 / 100
 376 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>

#define debug 
#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] , ini[MAXN] , fim[MAXN] ;

pii edge[MAXM] ;

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 ) 
{

	if( curRad == 0 ) return s ;

	debug("%d %lld\n" , s  ,curRad) ;
	lp(i,0,m) debug("%d " , allowed[i] == true ? 1 : 0) ;
	debug("\n") ;

	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] ;


}

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

vector<int> grupo[2] ;

void dfs(int x , int edgeId , int idx )
{

	for( Edge e : adj[x] )
		if( edgeId != e.id )
		{
			grupo[idx].pb(e.id) ;
			dfs(e.j,e.id, idx) ;
		}

}


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 ;
  	edge[i] = mk(a,b) ;

  }

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

  int l = 0 , r = m-1 , mid , best =0 ;

  while(l<=r)
  {

  	mid = (l+r)/2 ;

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

  	ll newTot = ask(toAsk) ;

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

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

  	else l = mid+1 ;

  }

  
  pii myEdge = edge[best] ;

  dfs(myEdge.ff , best , 0) ;
  dfs(myEdge.ss, best, 1) ;

  debug("Found %d %d\n" , myEdge.ff, myEdge.ss) ;

  for(int i : grupo[0]) debug("%d " ,  i) ;
  debug("\n") ;

  for(int i : grupo[1]) debug("%d " , i ) ;
  debug("\n") ;

	
	for(int i : grupo[0]) toAsk[i] = 1 ;

	ll newTot = (ask(toAsk) - Prev) / (B-A) ;

	
	memset(allowed, false, sizeof allowed) ;

	for(int i : grupo[0]) 
	{
		toAsk[i] = 0 ;
		allowed[i] = true ;
	}

	S = findSpecial( myEdge.ff , allowed , newTot ) ;

	for(int i : grupo[0]) allowed[i] = false ;
	for(int i : grupo[1]) allowed[i] = true ;

	T = findSpecial(myEdge.ss , allowed, rad  - newTot- 1) ;

	answer(S,T) ;

}

Compilation message

highway.cpp: In function 'int findSpecial(int, bool*, long long int)':
highway.cpp:72:22: warning: left operand of comma operator has no effect [-Wunused-value]
  debug("%d %lld\n" , s  ,curRad) ;
                      ^
highway.cpp:72:26: warning: right operand of comma operator has no effect [-Wunused-value]
  debug("%d %lld\n" , s  ,curRad) ;
                          ^~~~~~
highway.cpp:73:51: warning: left operand of comma operator has no effect [-Wunused-value]
  lp(i,0,m) debug("%d " , allowed[i] == true ? 1 : 0) ;
                                                   ^
highway.cpp:74:14: warning: statement has no effect [-Wunused-value]
  debug("\n") ;
              ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:8:12: warning: left operand of comma operator has no effect [-Wunused-value]
 #define ff first
            ^
highway.cpp:178:34: note: in expansion of macro 'ff'
   debug("Found %d %d\n" , myEdge.ff, myEdge.ss) ;
                                  ^~
highway.cpp:8:12: warning: right operand of comma operator has no effect [-Wunused-value]
 #define ff first
            ^
highway.cpp:178:34: note: in expansion of macro 'ff'
   debug("Found %d %d\n" , myEdge.ff, myEdge.ss) ;
                                  ^~
highway.cpp:180:40: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int i : grupo[0]) debug("%d " ,  i) ;
                                        ^
highway.cpp:181:15: warning: statement has no effect [-Wunused-value]
   debug("\n") ;
               ^
highway.cpp:183:39: warning: left operand of comma operator has no effect [-Wunused-value]
   for(int i : grupo[1]) debug("%d " , i ) ;
                                       ^
highway.cpp:184:15: warning: statement has no effect [-Wunused-value]
   debug("\n") ;
               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2580 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2608 KB Output is correct
4 Correct 4 ms 2604 KB Output is correct
5 Correct 4 ms 2572 KB Output is correct
6 Correct 4 ms 2668 KB Output is correct
7 Correct 5 ms 2584 KB Output is correct
8 Correct 4 ms 2576 KB Output is correct
9 Correct 4 ms 2584 KB Output is correct
10 Correct 4 ms 2580 KB Output is correct
11 Correct 4 ms 2572 KB Output is correct
12 Correct 4 ms 2576 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 17 ms 3408 KB Output is correct
3 Correct 184 ms 9352 KB Output is correct
4 Correct 199 ms 9352 KB Output is correct
5 Correct 183 ms 9436 KB Output is correct
6 Correct 180 ms 9340 KB Output is correct
7 Correct 187 ms 9356 KB Output is correct
8 Correct 217 ms 9344 KB Output is correct
9 Correct 203 ms 9268 KB Output is correct
10 Correct 219 ms 9340 KB Output is correct
11 Correct 230 ms 10204 KB Output is correct
12 Correct 199 ms 10972 KB Output is correct
13 Correct 229 ms 10516 KB Output is correct
14 Correct 238 ms 10508 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 3960 KB Output is correct
2 Correct 37 ms 5280 KB Output is correct
3 Correct 68 ms 6688 KB Output is correct
4 Correct 158 ms 13056 KB Output is correct
5 Correct 152 ms 13204 KB Output is correct
6 Correct 150 ms 14716 KB Output is correct
7 Correct 162 ms 15104 KB Output is correct
8 Correct 154 ms 13660 KB Output is correct
9 Correct 136 ms 13728 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2660 KB Output is correct
2 Correct 23 ms 3408 KB Output is correct
3 Correct 175 ms 7920 KB Output is correct
4 Correct 195 ms 9340 KB Output is correct
5 Correct 216 ms 9280 KB Output is correct
6 Correct 198 ms 9260 KB Output is correct
7 Correct 200 ms 9152 KB Output is correct
8 Correct 198 ms 9252 KB Output is correct
9 Correct 186 ms 9328 KB Output is correct
10 Correct 194 ms 9344 KB Output is correct
11 Correct 226 ms 10148 KB Output is correct
12 Correct 180 ms 11076 KB Output is correct
13 Correct 200 ms 10752 KB Output is correct
14 Correct 205 ms 10644 KB Output is correct
15 Correct 184 ms 9280 KB Output is correct
16 Correct 186 ms 9272 KB Output is correct
17 Correct 203 ms 10260 KB Output is correct
18 Correct 197 ms 10732 KB Output is correct
19 Correct 198 ms 9304 KB Output is correct
20 Correct 184 ms 11364 KB Output is correct
21 Correct 161 ms 10208 KB Output is correct
22 Correct 168 ms 10176 KB Output is correct
23 Correct 176 ms 9884 KB Output is correct
24 Correct 193 ms 10188 KB Output is correct
25 Correct 237 ms 14832 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 376 ms 262148 KB Execution killed with signal 9 (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 304 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -