oj.uz

Submission #116204

# Submission time Handle Problem Language Result Execution time Memory
116204 2019-06-11T09:00:55 Z claudy Highway Tolls (IOI18_highway) C++14
51 / 100
 460 ms 18352 KB 
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# define LOCAL
# define sim template < class c
# define ris return * this
# define dor > debug & operator <<
# define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define show(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
int gcd(int a, int b)
{
if(b) return gcd(b,a%b);
return a;
}mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

long long ask(const std::vector<int> &w);
void answer(int s, int t);

# define int ll

vector<int32_t>askvec;
int dist;
vector<pair<int,int>>vec[1 << 18];
vector<int>euler;
int M,N;
vector<int>f;
int viz[1 << 18];

void root(int nod)
{
	queue<int>Q;
	Q.push(nod);
	euler.clear();
	for(int i = 0;i < M;i++) askvec[i] = 0;
	for(int i = 0;i < N;i++) viz[i] = 0;
	viz[nod] = 1;
	f[nod] = -1;
	while(sz(Q))
	{
		int x = Q.front();
		Q.pop();
		euler.pb(x);
		for(auto it : vec[x])
		{
			if(!viz[it.first])
			{
				f[it.first] = it.second;
				askvec[it.second] = 1;
				Q.push(it.first);
				viz[it.first] = 1;
			}
		}
	}
	for(int i = 0;i < M;i++) askvec[i] = !askvec[i];
}

int bs()
{
	int l = 0;
	int r = N - 1;
	while(l < r)
	{
		int mid = l + r + 1 >> 1;
		mid += rng() % (min(10ll,r - mid + 1));
		mid = min(mid,r);
		for(int i = mid;i < N;i++)
		{
			if(f[euler[i]] != -1) askvec[f[euler[i]]] = 1;
		}
		if(ask(askvec) != dist) l = mid;
		else r = mid - 1;
		for(int i = mid;i < N;i++)
		{
			if(f[euler[i]] != -1) askvec[f[euler[i]]] = 0;
		}
	}
	return euler[l];
}
#undef int
void find_pair(int n, vector<int> U, vector<int> V, int A, int B) 
{
#define int ll
	N = n;
	M = sz(U);
	f.resize(N);
	for(int i = 0;i < sz(U);i++)
	{
		vec[U[i]].pb(mp(V[i],i));
		vec[V[i]].pb(mp(U[i],i));
	}	
	askvec.resize(M);
	for(int i = 0;i < M;i++) askvec[i] = 0;
	dist = ask(askvec);
	int l = 0;
	int r = N - 1;
	while(l < r)
	{
		int mid = (l + r >> 1);
		for(int i = 0;i < M;i++) askvec[i] = 0;
		for(int i = 0;i <= mid;i++)
		{
			for(auto it : vec[i])
			{
				askvec[it.second] = 1;
			}
		}
		if(ask(askvec) != dist) r = mid;
		else l = mid + 1;
	}
	root(l);
	int X = bs();
	root(X);
	int Y = bs();
	answer(X,Y);
}
/*
int32_t main(){_
	//freopen("input","r",stdin);

	return 0;
}*/

Compilation message

highway.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 # pragma GCC optimization ("unroll-loops")
 
highway.cpp: In function 'long long int bs()':
highway.cpp:102:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r + 1 >> 1;
             ~~~~~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:137:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = (l + r >> 1);
              ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6408 KB Output is correct
2 Correct 8 ms 6496 KB Output is correct
3 Correct 8 ms 6392 KB Output is correct
4 Correct 8 ms 6576 KB Output is correct
5 Correct 8 ms 6580 KB Output is correct
6 Correct 9 ms 6512 KB Output is correct
7 Correct 8 ms 6732 KB Output is correct
8 Correct 8 ms 6492 KB Output is correct
9 Correct 8 ms 6500 KB Output is correct
10 Correct 8 ms 6420 KB Output is correct
11 Correct 8 ms 6572 KB Output is correct
12 Correct 8 ms 6440 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6644 KB Output is correct
2 Correct 29 ms 7564 KB Output is correct
3 Correct 340 ms 15376 KB Output is correct
4 Correct 269 ms 15372 KB Output is correct
5 Correct 340 ms 15392 KB Output is correct
6 Correct 232 ms 15376 KB Output is correct
7 Correct 343 ms 15380 KB Output is correct
8 Correct 361 ms 15468 KB Output is correct
9 Correct 320 ms 15412 KB Output is correct
10 Correct 277 ms 15428 KB Output is correct
11 Correct 389 ms 15528 KB Output is correct
12 Correct 374 ms 15440 KB Output is correct
13 Correct 399 ms 15432 KB Output is correct
14 Correct 322 ms 15440 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 7464 KB Output is correct
2 Correct 50 ms 8420 KB Output is correct
3 Correct 81 ms 9352 KB Output is correct
4 Correct 149 ms 15032 KB Output is correct
5 Correct 209 ms 14952 KB Output is correct
6 Correct 182 ms 14932 KB Output is correct
7 Correct 233 ms 14936 KB Output is correct
8 Correct 192 ms 14976 KB Output is correct
9 Correct 216 ms 14960 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6612 KB Output is correct
2 Correct 30 ms 7568 KB Output is correct
3 Correct 291 ms 13680 KB Output is correct
4 Correct 422 ms 15388 KB Output is correct
5 Correct 347 ms 15476 KB Output is correct
6 Correct 409 ms 15456 KB Output is correct
7 Correct 366 ms 15340 KB Output is correct
8 Correct 403 ms 15344 KB Output is correct
9 Correct 324 ms 15376 KB Output is correct
10 Correct 365 ms 15372 KB Output is correct
11 Correct 338 ms 15444 KB Output is correct
12 Correct 293 ms 15424 KB Output is correct
13 Correct 373 ms 15428 KB Output is correct
14 Correct 389 ms 15448 KB Output is correct
15 Correct 396 ms 15452 KB Output is correct
16 Correct 403 ms 15376 KB Output is correct
17 Correct 354 ms 15436 KB Output is correct
18 Correct 364 ms 15432 KB Output is correct
19 Correct 386 ms 15380 KB Output is correct
20 Correct 388 ms 15452 KB Output is correct
21 Correct 351 ms 16504 KB Output is correct
22 Correct 321 ms 16384 KB Output is correct
23 Correct 249 ms 15752 KB Output is correct
24 Correct 268 ms 15696 KB Output is correct
25 Correct 266 ms 15508 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7556 KB Output is correct
2 Correct 31 ms 7716 KB Output is correct
3 Correct 326 ms 16208 KB Output is correct
4 Correct 405 ms 16908 KB Output is correct
5 Incorrect 460 ms 18352 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 7600 KB Output is correct
2 Correct 31 ms 7712 KB Output is correct
3 Incorrect 425 ms 16192 KB Output isn't correct
4 Halted 0 ms 0 KB -