oj.uz

Submission #1081690

# Submission time Handle Problem Language Result Execution time Memory
1081690 2024-08-30T09:15:27 Z GrindMachine Stations (IOI20_stations) C++17
76 / 100
 662 ms 1280 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define pb push_back
#define endl '\n'
#define conts continue
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define sz(a) (int)a.size()

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &x, T y){
	x = min(x,y);
}

template<typename T>
void amax(T &x, T y){
	x = max(x,y);
}

template<typename A,typename B>
string to_string(pair<A,B> p);

string to_string(const string &s){
	return "'"+s+"'";
}

string to_string(const char* s){
	return to_string((string)s);
}

string to_string(bool b){
	return b?"true":"false";
}

template<typename A>
string to_string(A v){
	string res = "{";
	trav(x,v){
		res += to_string(x)+",";
	}
	if(res.back() == ',') res.pop_back();
	res += "}";
	return res;
}

template<typename A,typename B>
string to_string(pair<A,B> p){
	return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}

#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;

#include "stations.h"

std::vector<int> label(int n, int k, std::vector<int> U, std::vector<int> V) {
	vector<vector<int>> adj(n);
	rep(i,n-1){
		int u = U[i], v = V[i];
		adj[u].pb(v), adj[v].pb(u);
	}

	vector<int> tin(n), tout(n), subsiz(n), depth(n);
	int timer = 0;

	auto dfs1 = [&](int u, int p, auto &&dfs1) -> void{
		tin[u] = timer++;
		subsiz[u] = 1;
		trav(v,adj[u]){
			if(v == p) conts;
			depth[v] = depth[u]+1;
			dfs1(v,u,dfs1);
			subsiz[u] += subsiz[v];
		}
		tout[u] = timer++;
	};

	dfs1(0,-1,dfs1);

	vector<int> ans(n);
	rep(i,n){
		if(depth[i]&1){
			ans[i] = tout[i];
		}
		else{
			ans[i] = tin[i];
		}
	}

	return ans;

	// std::vector<int> labels(n);
	// for (int i = 0; i < n; i++) {
	// 	labels[i] = i;
	// }
	// return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
	int typ = 1;
	trav(x,c){
		if(s < x){
			typ = 0;
			break;
		}
	}

	int p = -1;

	if(!typ){
		// tin
		if(s){
			p = c.back();
			c.pop_back();
		}

		int pv = s;
		trav(x,c){
			int tin = pv+1, tout = x;
			if(tin <= t and t <= tout){
				return x;
			}
			pv = tout;
		}

		return p;
	}
	else{
		// tout
		p = c[0];
		c.erase(c.begin());

		reverse(all(c));
		int pv = s;

		trav(x,c){
			int tin = x, tout = pv-1;
			if(tin <= t and t <= tout){
				return x;
			}
			pv = tin;
		}

		return p;
	}

	assert(0);
	return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Invalid labels (values out of range). scenario=2, k=1000, vertex=1, label=1990
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 344 KB Invalid labels (values out of range). scenario=0, k=1000, vertex=1, label=1022
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 377 ms 684 KB Output is correct
2 Correct 300 ms 908 KB Output is correct
3 Correct 616 ms 684 KB Output is correct
4 Correct 477 ms 684 KB Output is correct
5 Correct 401 ms 684 KB Output is correct
6 Correct 324 ms 684 KB Output is correct
7 Correct 274 ms 684 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Correct 393 ms 684 KB Output is correct
12 Correct 402 ms 764 KB Output is correct
13 Correct 301 ms 940 KB Output is correct
14 Correct 288 ms 684 KB Output is correct
15 Correct 41 ms 768 KB Output is correct
16 Correct 31 ms 684 KB Output is correct
17 Correct 67 ms 684 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 613 ms 684 KB Output is correct
2 Correct 476 ms 684 KB Output is correct
3 Correct 418 ms 688 KB Output is correct
4 Correct 1 ms 776 KB Output is correct
5 Correct 1 ms 768 KB Output is correct
6 Correct 0 ms 768 KB Output is correct
7 Correct 431 ms 684 KB Output is correct
8 Correct 612 ms 684 KB Output is correct
9 Correct 489 ms 684 KB Output is correct
10 Correct 397 ms 684 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 2 ms 776 KB Output is correct
13 Correct 3 ms 1280 KB Output is correct
14 Correct 1 ms 776 KB Output is correct
15 Correct 0 ms 764 KB Output is correct
16 Correct 330 ms 684 KB Output is correct
17 Correct 398 ms 684 KB Output is correct
18 Correct 364 ms 684 KB Output is correct
19 Correct 394 ms 684 KB Output is correct
20 Correct 361 ms 684 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 392 ms 684 KB Partially correct
2 Partially correct 342 ms 684 KB Partially correct
3 Correct 662 ms 684 KB Output is correct
4 Correct 504 ms 684 KB Output is correct
5 Correct 429 ms 684 KB Output is correct
6 Partially correct 310 ms 684 KB Partially correct
7 Partially correct 312 ms 684 KB Partially correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 0 ms 776 KB Output is correct
11 Partially correct 362 ms 684 KB Partially correct
12 Partially correct 372 ms 684 KB Partially correct
13 Correct 641 ms 684 KB Output is correct
14 Correct 449 ms 936 KB Output is correct
15 Correct 414 ms 684 KB Output is correct
16 Partially correct 277 ms 684 KB Partially correct
17 Correct 357 ms 684 KB Output is correct
18 Partially correct 309 ms 992 KB Partially correct
19 Partially correct 336 ms 1008 KB Partially correct
20 Partially correct 298 ms 684 KB Partially correct
21 Correct 31 ms 764 KB Output is correct
22 Partially correct 52 ms 776 KB Partially correct
23 Partially correct 67 ms 680 KB Partially correct
24 Correct 4 ms 768 KB Output is correct
25 Correct 4 ms 768 KB Output is correct
26 Correct 2 ms 768 KB Output is correct
27 Correct 1 ms 768 KB Output is correct
28 Correct 0 ms 776 KB Output is correct
29 Correct 379 ms 688 KB Output is correct
30 Correct 347 ms 684 KB Output is correct
31 Correct 370 ms 684 KB Output is correct
32 Correct 359 ms 684 KB Output is correct
33 Correct 350 ms 684 KB Output is correct
34 Partially correct 236 ms 684 KB Partially correct
35 Partially correct 278 ms 684 KB Partially correct
36 Partially correct 289 ms 912 KB Partially correct
37 Partially correct 335 ms 768 KB Partially correct
38 Partially correct 334 ms 684 KB Partially correct
39 Partially correct 332 ms 1012 KB Partially correct
40 Partially correct 313 ms 1268 KB Partially correct
41 Partially correct 298 ms 768 KB Partially correct
42 Partially correct 28 ms 716 KB Partially correct
43 Partially correct 61 ms 768 KB Partially correct
44 Partially correct 108 ms 744 KB Partially correct
45 Partially correct 99 ms 684 KB Partially correct
46 Partially correct 210 ms 940 KB Partially correct
47 Partially correct 213 ms 684 KB Partially correct
48 Partially correct 35 ms 716 KB Partially correct
49 Partially correct 35 ms 940 KB Partially correct