oj.uz

Submission #288190

# Submission time Handle Problem Language Result Execution time Memory
288190 2020-09-01T09:42:43 Z infinite_iq Highway Tolls (IOI18_highway) C++14
5 / 100
 257 ms 262148 KB 
#include <bits/stdc++.h>
using namespace std ;
#define mid (l+r)/2
#define pb push_back
#define fi first 
#define se second 
#define C continue 
typedef long long ll ;
typedef pair < int , int > pi ;
typedef vector < int > vi ;
typedef vector < ll  > vll ;
typedef vector < pi > vpi ;
#include "highway.h"
ll n , m , len , XXX , num ;
vpi v [100009] ;
vi no ;
ll yes [100009] ;
ll query ( vi ret ) {
  num ++ ;
  if ( num > 60 ) {
    cout << 5 / 0 << endl ;
  }
        vi v ( m , 0 ) ;
        for ( auto u : ret ) v [u] = 1 ;
        return ask (v) ;
}
void fill ( int node , int p , int lev ) {
        yes [node] = ( lev == len ) ;
        for ( auto u : v [node] ) {
                if ( u .fi == p ) C ;
                fill ( u .fi , node , lev + 1 ) ;
                yes [node] = max ( yes [node] , yes [u.fi] ) ;
        }
}
void dfs ( int node , int p , int lev ) {
        if ( lev == len ) {
                answer ( 0 , node ) ;
                return ;
        }
        vpi ret ;
        for ( auto u : v [node] ) {
                if ( u .fi == p ) C ;
                if ( !yes [u.fi] ) C ;
                ret .pb ( u ) ;
        }
  if ( ret .size () == 0 ) {
    
    while ( 1 ) {
      
    }
  }
        int l = -1 , r = ret .size () - 1 ;
        while ( r - l > 1 ) {
                vi crnt ;
                for ( int i = mid + 1 ; i <= r ; i ++ ) {
                        crnt .pb ( ret [i] .se ) ;
                }
                int cost = query ( crnt ) ;
                if ( cost == len * XXX ) {
                        r = mid ;
                }
                else {
                        l = mid ;
                }
        }
        dfs ( ret [r].fi , node , lev + 1 ) ;
}
void find_pair ( int N , vi U, vi V , int A , int B ) {
        n = N , m = U .size () , len = query ( no ) / A , XXX = A ;
        for ( int i = 0 ; i < m ; i ++ ) {
                int a = U [i] , b = V [i] ;
                v [a] .pb ( { b , i } ) ;
                v [b] .pb ( { a , i } ) ;
        }
        fill ( 0 , 0 , 0 ) ;
        dfs  ( 0 , 0 , 0 ) ;
}

Compilation message

highway.cpp: In function 'll query(vi)':
highway.cpp:21:15: warning: division by zero [-Wdiv-by-zero]
   21 |     cout << 5 / 0 << endl ;
      |             ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2728 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2732 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 13 ms 3328 KB Output is correct
3 Correct 134 ms 8472 KB Output is correct
4 Correct 125 ms 8472 KB Output is correct
5 Correct 122 ms 8472 KB Output is correct
6 Correct 126 ms 8564 KB Output is correct
7 Correct 126 ms 8472 KB Output is correct
8 Correct 120 ms 8472 KB Output is correct
9 Correct 135 ms 8600 KB Output is correct
10 Correct 126 ms 8472 KB Output is correct
11 Correct 125 ms 9752 KB Output is correct
12 Correct 129 ms 10776 KB Output is correct
13 Correct 126 ms 10136 KB Output is correct
14 Incorrect 123 ms 10008 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

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