oj.uz

Submission #116198

# Submission time Handle Problem Language Result Execution time Memory
116198 2019-06-11T08:48:25 Z claudy Highway Tolls (IOI18_highway) C++14
90 / 100
 503 ms 18516 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;
		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:135: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 6608 KB Output is correct
2 Correct 8 ms 6392 KB Output is correct
3 Correct 8 ms 6496 KB Output is correct
4 Correct 8 ms 6488 KB Output is correct
5 Correct 8 ms 6384 KB Output is correct
6 Correct 8 ms 6492 KB Output is correct
7 Correct 8 ms 6488 KB Output is correct
8 Correct 8 ms 6492 KB Output is correct
9 Correct 8 ms 6580 KB Output is correct
10 Correct 8 ms 6488 KB Output is correct
11 Correct 8 ms 6392 KB Output is correct
12 Correct 8 ms 6392 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6520 KB Output is correct
2 Correct 34 ms 7564 KB Output is correct
3 Correct 326 ms 15380 KB Output is correct
4 Correct 280 ms 15448 KB Output is correct
5 Correct 348 ms 15380 KB Output is correct
6 Correct 267 ms 15384 KB Output is correct
7 Correct 343 ms 15392 KB Output is correct
8 Correct 375 ms 15392 KB Output is correct
9 Correct 328 ms 15384 KB Output is correct
10 Correct 331 ms 15380 KB Output is correct
11 Correct 380 ms 15460 KB Output is correct
12 Correct 373 ms 15432 KB Output is correct
13 Correct 370 ms 15436 KB Output is correct
14 Correct 294 ms 15432 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 7456 KB Output is correct
2 Correct 48 ms 8504 KB Output is correct
3 Correct 73 ms 9352 KB Output is correct
4 Correct 203 ms 15008 KB Output is correct
5 Correct 187 ms 14992 KB Output is correct
6 Correct 139 ms 14992 KB Output is correct
7 Correct 214 ms 14940 KB Output is correct
8 Correct 190 ms 14988 KB Output is correct
9 Correct 219 ms 15016 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6520 KB Output is correct
2 Correct 36 ms 7524 KB Output is correct
3 Correct 290 ms 13720 KB Output is correct
4 Correct 390 ms 15400 KB Output is correct
5 Correct 336 ms 15452 KB Output is correct
6 Correct 407 ms 15412 KB Output is correct
7 Correct 359 ms 15444 KB Output is correct
8 Correct 396 ms 15416 KB Output is correct
9 Correct 319 ms 15384 KB Output is correct
10 Correct 346 ms 15388 KB Output is correct
11 Correct 281 ms 15492 KB Output is correct
12 Correct 281 ms 15444 KB Output is correct
13 Correct 342 ms 15508 KB Output is correct
14 Correct 348 ms 15436 KB Output is correct
15 Correct 418 ms 15380 KB Output is correct
16 Correct 402 ms 15388 KB Output is correct
17 Correct 357 ms 15432 KB Output is correct
18 Correct 382 ms 15440 KB Output is correct
19 Correct 367 ms 15372 KB Output is correct
20 Correct 377 ms 15440 KB Output is correct
21 Correct 338 ms 16508 KB Output is correct
22 Correct 332 ms 16500 KB Output is correct
23 Correct 258 ms 15764 KB Output is correct
24 Correct 240 ms 15648 KB Output is correct
25 Correct 224 ms 15440 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 7604 KB Output is correct
2 Correct 36 ms 7680 KB Output is correct
3 Correct 355 ms 16200 KB Output is correct
4 Correct 397 ms 16960 KB Output is correct
5 Correct 472 ms 18356 KB Output is correct
6 Correct 432 ms 18400 KB Output is correct
7 Correct 477 ms 18516 KB Output is correct
8 Correct 421 ms 18440 KB Output is correct
9 Correct 307 ms 15272 KB Output is correct
10 Correct 299 ms 16360 KB Output is correct
11 Correct 343 ms 16800 KB Output is correct
12 Correct 415 ms 18096 KB Output is correct
13 Correct 375 ms 18192 KB Output is correct
14 Correct 402 ms 18392 KB Output is correct
15 Correct 439 ms 18392 KB Output is correct
16 Correct 315 ms 17032 KB Output is correct
17 Correct 279 ms 15808 KB Output is correct
18 Correct 294 ms 16108 KB Output is correct
19 Correct 299 ms 15804 KB Output is correct
20 Correct 358 ms 15952 KB Output is correct
21 Correct 468 ms 18392 KB Output is correct

Subtask #6
21.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 7544 KB Output is correct
2 Correct 37 ms 7672 KB Output is correct
3 Partially correct 417 ms 16164 KB Output is partially correct
4 Partially correct 376 ms 16500 KB Output is partially correct
5 Correct 383 ms 16944 KB Output is correct
6 Partially correct 425 ms 18404 KB Output is partially correct
7 Partially correct 407 ms 16244 KB Output is partially correct
8 Correct 413 ms 16564 KB Output is correct
9 Partially correct 438 ms 16932 KB Output is partially correct
10 Correct 420 ms 18396 KB Output is correct
11 Partially correct 498 ms 18408 KB Output is partially correct
12 Partially correct 440 ms 18404 KB Output is partially correct
13 Correct 345 ms 16884 KB Output is correct
14 Correct 309 ms 16356 KB Output is correct
15 Correct 346 ms 16800 KB Output is correct
16 Correct 294 ms 16532 KB Output is correct
17 Correct 376 ms 16824 KB Output is correct
18 Correct 305 ms 16360 KB Output is correct
19 Correct 416 ms 18012 KB Output is correct
20 Correct 437 ms 18220 KB Output is correct
21 Correct 417 ms 18488 KB Output is correct
22 Partially correct 436 ms 18372 KB Output is partially correct
23 Correct 421 ms 18428 KB Output is correct
24 Partially correct 457 ms 18428 KB Output is partially correct
25 Partially correct 503 ms 18388 KB Output is partially correct
26 Correct 421 ms 18424 KB Output is correct
27 Partially correct 329 ms 16076 KB Output is partially correct
28 Partially correct 314 ms 15788 KB Output is partially correct
29 Partially correct 364 ms 16364 KB Output is partially correct
30 Correct 317 ms 15844 KB Output is correct
31 Partially correct 322 ms 15944 KB Output is partially correct
32 Correct 283 ms 15776 KB Output is correct
33 Correct 295 ms 16480 KB Output is correct
34 Correct 304 ms 15944 KB Output is correct
35 Partially correct 347 ms 15844 KB Output is partially correct
36 Correct 300 ms 15732 KB Output is correct
37 Correct 377 ms 16200 KB Output is correct
38 Partially correct 320 ms 15888 KB Output is partially correct
39 Correct 446 ms 18396 KB Output is correct
40 Correct 467 ms 18388 KB Output is correct
41 Correct 373 ms 18436 KB Output is correct
42 Partially correct 451 ms 18436 KB Output is partially correct