oj.uz

Submission #305107

# Submission time Handle Problem Language Result Execution time Memory
305107 2020-09-22T15:18:58 Z Gajowy Stations (IOI20_stations) C++14
100 / 100
 1236 ms 1152 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define e1 first
#define e2 second
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define ld long double
#define float long double
#define size(x) (int)x.size()
#define satori int testCases; cin>>testCases; while(testCases--)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(r) begin(r),end(r)
#define time chrono::high_resolution_clock().now().time_since_epoch().count()
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int MAXN=1e3+10;

int id[MAXN],ct;
vector<int> g[MAXN];

void dfs(int u,int p,int d)
{
	if(d)
		id[u]=ct++;
	for(auto v:g[u])
		if(v!=p)
			dfs(v,u,d^1);
	if(!d)
		id[u]=ct++;
}

vector<int> label(int n,int k,vector<int> a,vector<int> b)
{
	vector<int> res(n); 
	for(int i=0;i<n;i++)
		g[i].clear();
	ct=0;
	for(int i=0;i<n-1;i++)
		g[a[i]].eb(b[i]),g[b[i]].eb(a[i]);
	ct=0;
	dfs(0,-1,0);
	for(int i=0;i<n;i++)
		res[i]=id[i];
	return res;
}


int find_next_station(int s,int t,vector<int> c)
{
	if(size(c)==1)
		return c[0];
	if(s<c[0])
	{
		if(t<s)
			return c.back();
		for(auto xd:c)
			if(xd>=t)
				return xd;
		return c.back();
	}
	else
	{
		if(t>s)
			return c[0];
		reverse(all(c));
		for(auto xd:c)
			if(xd<=t)
				return xd;
		return c.back();
	}
	return -1;
}

Compilation message

stations.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("O3")
      | 
stations.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 1032 KB Output is correct
2 Correct 481 ms 1024 KB Output is correct
3 Correct 913 ms 768 KB Output is correct
4 Correct 821 ms 768 KB Output is correct
5 Correct 701 ms 768 KB Output is correct
6 Correct 568 ms 1024 KB Output is correct
7 Correct 481 ms 780 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 2 ms 896 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 776 KB Output is correct
2 Correct 550 ms 768 KB Output is correct
3 Correct 1053 ms 904 KB Output is correct
4 Correct 821 ms 792 KB Output is correct
5 Correct 653 ms 768 KB Output is correct
6 Correct 597 ms 768 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 1048 KB Output is correct
2 Correct 632 ms 1024 KB Output is correct
3 Correct 972 ms 896 KB Output is correct
4 Correct 732 ms 768 KB Output is correct
5 Correct 706 ms 904 KB Output is correct
6 Correct 678 ms 1024 KB Output is correct
7 Correct 558 ms 800 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 6 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 836 ms 768 KB Output is correct
12 Correct 516 ms 1024 KB Output is correct
13 Correct 559 ms 1152 KB Output is correct
14 Correct 602 ms 768 KB Output is correct
15 Correct 58 ms 768 KB Output is correct
16 Correct 96 ms 776 KB Output is correct
17 Correct 112 ms 896 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1168 ms 768 KB Output is correct
2 Correct 824 ms 868 KB Output is correct
3 Correct 719 ms 792 KB Output is correct
4 Correct 3 ms 768 KB Output is correct
5 Correct 6 ms 904 KB Output is correct
6 Correct 2 ms 800 KB Output is correct
7 Correct 633 ms 768 KB Output is correct
8 Correct 974 ms 776 KB Output is correct
9 Correct 751 ms 768 KB Output is correct
10 Correct 659 ms 776 KB Output is correct
11 Correct 5 ms 896 KB Output is correct
12 Correct 6 ms 904 KB Output is correct
13 Correct 7 ms 768 KB Output is correct
14 Correct 5 ms 768 KB Output is correct
15 Correct 2 ms 800 KB Output is correct
16 Correct 640 ms 768 KB Output is correct
17 Correct 541 ms 896 KB Output is correct
18 Correct 501 ms 1056 KB Output is correct
19 Correct 489 ms 792 KB Output is correct
20 Correct 717 ms 800 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 817 ms 888 KB Output is correct
2 Correct 511 ms 1024 KB Output is correct
3 Correct 1004 ms 776 KB Output is correct
4 Correct 783 ms 1024 KB Output is correct
5 Correct 836 ms 776 KB Output is correct
6 Correct 590 ms 1152 KB Output is correct
7 Correct 567 ms 896 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 2 ms 904 KB Output is correct
11 Correct 631 ms 824 KB Output is correct
12 Correct 806 ms 896 KB Output is correct
13 Correct 1236 ms 768 KB Output is correct
14 Correct 676 ms 768 KB Output is correct
15 Correct 639 ms 856 KB Output is correct
16 Correct 522 ms 768 KB Output is correct
17 Correct 703 ms 768 KB Output is correct
18 Correct 461 ms 1008 KB Output is correct
19 Correct 585 ms 1024 KB Output is correct
20 Correct 701 ms 780 KB Output is correct
21 Correct 63 ms 808 KB Output is correct
22 Correct 94 ms 768 KB Output is correct
23 Correct 142 ms 768 KB Output is correct
24 Correct 7 ms 768 KB Output is correct
25 Correct 7 ms 768 KB Output is correct
26 Correct 5 ms 876 KB Output is correct
27 Correct 5 ms 768 KB Output is correct
28 Correct 1 ms 768 KB Output is correct
29 Correct 606 ms 876 KB Output is correct
30 Correct 687 ms 768 KB Output is correct
31 Correct 723 ms 768 KB Output is correct
32 Correct 753 ms 792 KB Output is correct
33 Correct 749 ms 768 KB Output is correct
34 Correct 335 ms 1024 KB Output is correct
35 Correct 532 ms 1008 KB Output is correct
36 Correct 556 ms 1144 KB Output is correct
37 Correct 750 ms 884 KB Output is correct
38 Correct 565 ms 768 KB Output is correct
39 Correct 447 ms 1032 KB Output is correct
40 Correct 492 ms 1024 KB Output is correct
41 Correct 528 ms 768 KB Output is correct
42 Correct 76 ms 768 KB Output is correct
43 Correct 116 ms 888 KB Output is correct
44 Correct 134 ms 896 KB Output is correct
45 Correct 158 ms 968 KB Output is correct
46 Correct 411 ms 768 KB Output is correct
47 Correct 320 ms 896 KB Output is correct
48 Correct 77 ms 808 KB Output is correct
49 Correct 80 ms 1024 KB Output is correct