oj.uz

Submission #1067357

# Submission time Handle Problem Language Result Execution time Memory
1067357 2024-08-20T15:31:22 Z Lalic Stations (IOI20_stations) C++17
0 / 100
 584 ms 1020 KB 
#include "stations.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(). x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int INF = 0x3f3f3f3f;

void build(int ver, int prev, vector<int>& labels, bool isMax, int& cnt, vector<vector<int>>& adj, vector<int>& submin, vector<int>& submax){
	if(prev!=-1 && (int)adj[ver].size()==1){
		labels[ver]=cnt;
		submin[ver]=submax[ver]=cnt;
		cnt++;
		return;
	}
	
	int mx=-INF, mn=INF;
	for(auto u : adj[ver]){
		if(u==prev) continue;
		build(u, ver, labels, !isMax, cnt, adj, submin, submax);
		mx=max(mx, submax[u]);
		mn=min(mn, submin[u]);
	}
	
	if(isMax){
		labels[ver]=submax[ver]=mx+1;
		submin[ver]=mn;
		if(mx+1>=cnt) cnt=mx+2;
	}
	else{
		labels[ver]=submin[ver]=mn-1;
		submax[ver]=mx;
	}
}

vector<int> label(int n, int k, vector<int> u, vector<int> v) {
	vector<int> labels(n);
	vector<vector<int>> adj(n);
	vector<int> submin(n), submax(n);
	
	for(int i=0;i<n-1;i++){
		adj[u[i]].pb(v[i]);
		adj[v[i]].pb(u[i]);
	}
	
	int aux=0;
	build(0, -1, labels, 0, aux, adj, submin, submax);
	
	vector<pii> proc;
	for(int i=0;i<n;i++) proc.pb({labels[i], i});
	
	sort(all(proc));
	
	//~ for(int i=0;i<n;i++) cout << labels[i] << " \n"[i==n-1];
	
	for(int i=0;i<n;i++) labels[proc[i].se]=i;
	
	//~ for(int i=0;i<n;i++) cout << labels[i] << " \n"[i==n-1];
	
	return labels;
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 358 ms 940 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 684 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 370 ms 940 KB Wrong query response.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 684 KB Output is correct
2 Correct 422 ms 684 KB Output is correct
3 Correct 423 ms 684 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 776 KB Output is correct
7 Correct 432 ms 684 KB Output is correct
8 Correct 584 ms 684 KB Output is correct
9 Correct 471 ms 684 KB Output is correct
10 Correct 422 ms 684 KB Output is correct
11 Correct 4 ms 1020 KB Output is correct
12 Correct 3 ms 784 KB Output is correct
13 Correct 3 ms 776 KB Output is correct
14 Correct 2 ms 776 KB Output is correct
15 Correct 1 ms 768 KB Output is correct
16 Incorrect 336 ms 684 KB Wrong query response.
17 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 360 ms 940 KB Wrong query response.
2 Halted 0 ms 0 KB -