oj.uz

Submission #730750

# Submission time Handle Problem Language Result Execution time Memory
730750 2023-04-26T11:00:29 Z sentheta Stations (IOI20_stations) C++17
100 / 100
 930 ms 1196 KB 
#include "stations.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 1005;

V<int> adj[N];

int d[N];
int in[N], out[N];
int t = 0;
void dfs(int x=0,int par=-1){
	in[x] = t++;
	for(int y : adj[x]) if(y!=par){
		d[y] = d[x]+1;
		dfs(y, x);
	}
	out[x] = t++;
}

V<int> label(int n,int k,V<int> u,V<int> v){
	rep(i,0,n){
		adj[i].clear();
	}
	rep(i,0,n-1){
		adj[u[i]].push_back(v[i]);
		adj[v[i]].push_back(u[i]);
	}

	t = 0;
	dfs();

	map<int,int> zip;
	rep(i,0,n){
		if(d[i]%2==0) zip[in[i]];
		else zip[out[i]];
	}
	t = 0;
	for(auto&[p,q] : zip) q = t++;

	V<int> ans;
	rep(i,0,n){
		if(d[i]%2==0) ans.push_back(zip[in[i]]);
		else ans.push_back(zip[out[i]]);
	}

	return ans;
}

int find_next_station(int s,int t,V<int> c){
	// s is in[x]
	if(s < c[0]){
		int par = s==0 ? -1 : c.back();

		int l = s+1;
		for(int r : c) if(r!=par){
			if(l<=t && t<=r) return r;
			l = r+1;
		}
		return par;
	}
	// s is out[x]
	else{
		int par = c[0];

		c.push_back(s);
		rep(i,0,c.size()-1){
			if(c[i]<=t && t<=c[i+1]-1) return c[i];
		}
		return par;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 784 KB Output is correct
2 Correct 399 ms 672 KB Output is correct
3 Correct 895 ms 536 KB Output is correct
4 Correct 682 ms 544 KB Output is correct
5 Correct 648 ms 536 KB Output is correct
6 Correct 548 ms 672 KB Output is correct
7 Correct 485 ms 700 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 5 ms 488 KB Output is correct
10 Correct 2 ms 628 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 532 KB Output is correct
2 Correct 530 ms 548 KB Output is correct
3 Correct 904 ms 540 KB Output is correct
4 Correct 708 ms 516 KB Output is correct
5 Correct 666 ms 548 KB Output is correct
6 Correct 522 ms 524 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 561 ms 804 KB Output is correct
2 Correct 470 ms 688 KB Output is correct
3 Correct 905 ms 540 KB Output is correct
4 Correct 693 ms 416 KB Output is correct
5 Correct 644 ms 672 KB Output is correct
6 Correct 414 ms 800 KB Output is correct
7 Correct 444 ms 700 KB Output is correct
8 Correct 1 ms 756 KB Output is correct
9 Correct 4 ms 628 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 513 ms 540 KB Output is correct
12 Correct 528 ms 792 KB Output is correct
13 Correct 521 ms 784 KB Output is correct
14 Correct 424 ms 540 KB Output is correct
15 Correct 57 ms 624 KB Output is correct
16 Correct 59 ms 700 KB Output is correct
17 Correct 118 ms 672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 520 KB Output is correct
2 Correct 645 ms 420 KB Output is correct
3 Correct 636 ms 532 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 4 ms 756 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 541 ms 512 KB Output is correct
8 Correct 809 ms 532 KB Output is correct
9 Correct 684 ms 540 KB Output is correct
10 Correct 573 ms 668 KB Output is correct
11 Correct 5 ms 620 KB Output is correct
12 Correct 5 ms 756 KB Output is correct
13 Correct 4 ms 620 KB Output is correct
14 Correct 4 ms 748 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Correct 528 ms 544 KB Output is correct
17 Correct 415 ms 548 KB Output is correct
18 Correct 526 ms 548 KB Output is correct
19 Correct 523 ms 544 KB Output is correct
20 Correct 532 ms 536 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 576 ms 816 KB Output is correct
2 Correct 536 ms 816 KB Output is correct
3 Correct 917 ms 512 KB Output is correct
4 Correct 590 ms 532 KB Output is correct
5 Correct 570 ms 544 KB Output is correct
6 Correct 415 ms 824 KB Output is correct
7 Correct 429 ms 672 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 2 ms 616 KB Output is correct
11 Correct 505 ms 544 KB Output is correct
12 Correct 541 ms 548 KB Output is correct
13 Correct 930 ms 516 KB Output is correct
14 Correct 681 ms 540 KB Output is correct
15 Correct 575 ms 416 KB Output is correct
16 Correct 415 ms 548 KB Output is correct
17 Correct 532 ms 544 KB Output is correct
18 Correct 387 ms 912 KB Output is correct
19 Correct 475 ms 780 KB Output is correct
20 Correct 458 ms 536 KB Output is correct
21 Correct 63 ms 576 KB Output is correct
22 Correct 80 ms 672 KB Output is correct
23 Correct 104 ms 676 KB Output is correct
24 Correct 5 ms 632 KB Output is correct
25 Correct 5 ms 744 KB Output is correct
26 Correct 4 ms 620 KB Output is correct
27 Correct 3 ms 628 KB Output is correct
28 Correct 1 ms 616 KB Output is correct
29 Correct 453 ms 672 KB Output is correct
30 Correct 519 ms 676 KB Output is correct
31 Correct 606 ms 548 KB Output is correct
32 Correct 565 ms 536 KB Output is correct
33 Correct 530 ms 676 KB Output is correct
34 Correct 362 ms 668 KB Output is correct
35 Correct 379 ms 788 KB Output is correct
36 Correct 486 ms 744 KB Output is correct
37 Correct 439 ms 784 KB Output is correct
38 Correct 534 ms 1196 KB Output is correct
39 Correct 499 ms 784 KB Output is correct
40 Correct 477 ms 800 KB Output is correct
41 Correct 468 ms 800 KB Output is correct
42 Correct 71 ms 828 KB Output is correct
43 Correct 132 ms 708 KB Output is correct
44 Correct 139 ms 736 KB Output is correct
45 Correct 171 ms 652 KB Output is correct
46 Correct 330 ms 540 KB Output is correct
47 Correct 315 ms 708 KB Output is correct
48 Correct 74 ms 800 KB Output is correct
49 Correct 69 ms 892 KB Output is correct