oj.uz

Submission #828412

# Submission time Handle Problem Language Result Execution time Memory
828412 2023-08-17T09:24:11 Z minhcool Stations (IOI20_stations) C++17
76 / 100
 734 ms 24268 KB 
#include "stations.h"
#include<bits/stdc++.h>
using namespace std;
#include <vector>
 
#define pb push_back
#define fi first
#define se second
#define pb push_back

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 5e5 + 5, oo = 1e18 + 7;
 
int n;
vector<int> Adj[N];
 
int l[N], r[N], d[N];
 
vector<int> vis;
 
void dfs(int u, int p){
	vis.pb(u);
	l[u] = vis.size();
	for(auto v : Adj[u]){
		if(v == p) continue;
		d[v] = d[u] + 1;
		dfs(v, u);
		vis.pb(u);
	}
	//vis.pb(u);
	r[u] = vis.size();
}
 
//vector<int> vis;
 
int tol[1005][1005];
ii tol2[600005];
 
/*
void prep(){
	int cnt = 0;
	for(int i = 1; i <= 1000; i++){
		for(int j = i; j <= 1000; j++){
			tol[i][j] = cnt;
			tol2[cnt] = {i, j};
			cnt++;
		}
	}
}*/
 
vector<int> label(int n_, int k, vector<int> u, vector<int> v) {
	n = n_;
	vis.clear();
	for(int i = 0; i < n; i++) Adj[i].clear();
	for(int i = 0; i < (n - 1); i++){
		Adj[u[i]].pb(v[i]); Adj[v[i]].pb(u[i]);
	}
	dfs(0, 0);
	vector<int> labels(n);
	for(int i = 0; i < n; i++){
		//cout << l[i] << " " << r[i] << " " << tol[l[i]][r[i]] << "\n";
		//labels[i] = tol[l[i]][r[i]];
		if(!(d[i] & 1)) labels[i] = l[i];
		else labels[i] = r[i];
	}
	return labels;
	/*
	std::vector<int> labels(n);
	for (int i = 0; i < n; i++) {
		labels[i] = i;
	}
	return labels;*/
}

/*
bool anc(int lab1, int lab2){
	ii temp1 = {lab1 / 1000 + 1, lab1 % 1000 + 1}, temp2 = {lab2 / 1000 + 1, lab2 % 1000 + 1};
	return (temp1.fi <= temp2.fi && temp1.se >= temp2.se);
}*/
 
int find_next_station(int s, int t, vector<int> c) {
	//cout << c.size() << "\n";
	//return 0;
	int mini = oo;
	for(auto it : c) mini = min(mini, it);
	if(mini < s){// which means that s is right
		for(int i = 1; i < c.size(); i++){
			int le = c[i], ri;
			if(i != c.size() - 1) ri = c[i + 1] - 1;
			else ri = s;
			if(le <= t && ri >= t) return c[i];
		}
		return c[0];
	}
	else{
		//cout << s << " " << t << " " << "OK\n";
		for(int i = 0; (i + 1) < c.size(); i++){
			int le = (i ? c[i - 1] + 1 : s + 1), ri = c[i];
			if(le <= t && ri >= t) return c[i];
		}
		return c.back();
	}
	/*
	pair<int, int> mini = {oo, oo}, maxi = {-1, -1};
	for(int i = 0; i < c.size(); i++){
		ii tempo = {c[i] / 1000 + 1, c[i] % 1000 + 1};
		maxi = max(maxi, {tempo.se - tempo.fi + 1, c[i]});
		if(anc(c[i], t)){
			mini = min(mini, {tempo.se - tempo.fi + 1, c[i]});
		}
	}
	if(mini.se != oo) return mini.se;
	else return maxi.se;
	if(anc(c[1], t)) return c[1];
    else if(anc(c[2], t)) return c[2];
    else return c[0];*/
	//return c[0];
}

Compilation message

stations.cpp:15:34: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   15 | const int N = 5e5 + 5, oo = 1e18 + 7;
      |                             ~~~~~^~~
stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |   for(int i = 1; i < c.size(); i++){
      |                  ~~^~~~~~~~~~
stations.cpp:92:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |    if(i != c.size() - 1) ri = c[i + 1] - 1;
      |       ~~^~~~~~~~~~~~~~~
stations.cpp:100:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for(int i = 0; (i + 1) < c.size(); i++){
      |                  ~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 12208 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 7 ms 12136 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 373 ms 24200 KB Output is correct
2 Correct 314 ms 24168 KB Output is correct
3 Correct 674 ms 24036 KB Output is correct
4 Correct 594 ms 24036 KB Output is correct
5 Correct 415 ms 24060 KB Output is correct
6 Correct 387 ms 24236 KB Output is correct
7 Correct 344 ms 24172 KB Output is correct
8 Correct 11 ms 24088 KB Output is correct
9 Correct 11 ms 24068 KB Output is correct
10 Correct 10 ms 24080 KB Output is correct
11 Correct 428 ms 24040 KB Output is correct
12 Correct 376 ms 24160 KB Output is correct
13 Correct 317 ms 24224 KB Output is correct
14 Correct 496 ms 24040 KB Output is correct
15 Correct 45 ms 24008 KB Output is correct
16 Correct 70 ms 24096 KB Output is correct
17 Correct 100 ms 24140 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 24040 KB Output is correct
2 Correct 417 ms 23972 KB Output is correct
3 Correct 461 ms 23968 KB Output is correct
4 Correct 10 ms 24100 KB Output is correct
5 Correct 13 ms 24156 KB Output is correct
6 Correct 11 ms 24080 KB Output is correct
7 Correct 406 ms 24040 KB Output is correct
8 Correct 640 ms 24028 KB Output is correct
9 Correct 416 ms 23968 KB Output is correct
10 Correct 385 ms 24032 KB Output is correct
11 Correct 16 ms 24088 KB Output is correct
12 Correct 13 ms 24140 KB Output is correct
13 Correct 13 ms 24080 KB Output is correct
14 Correct 13 ms 24084 KB Output is correct
15 Correct 10 ms 24088 KB Output is correct
16 Correct 282 ms 23972 KB Output is correct
17 Correct 437 ms 24204 KB Output is correct
18 Correct 501 ms 23968 KB Output is correct
19 Correct 407 ms 23960 KB Output is correct
20 Correct 387 ms 24096 KB Output is correct

Subtask #5
50.0 / 61.0

# Verdict Execution time Memory Grader output
1 Partially correct 476 ms 24096 KB Partially correct
2 Partially correct 423 ms 24100 KB Partially correct
3 Correct 693 ms 24032 KB Output is correct
4 Correct 613 ms 24040 KB Output is correct
5 Correct 402 ms 23968 KB Output is correct
6 Partially correct 408 ms 24088 KB Partially correct
7 Partially correct 324 ms 24100 KB Partially correct
8 Correct 13 ms 24080 KB Output is correct
9 Correct 12 ms 24132 KB Output is correct
10 Correct 10 ms 24080 KB Output is correct
11 Partially correct 394 ms 24100 KB Partially correct
12 Partially correct 389 ms 24096 KB Partially correct
13 Correct 725 ms 24036 KB Output is correct
14 Correct 573 ms 24096 KB Output is correct
15 Correct 535 ms 24116 KB Output is correct
16 Partially correct 347 ms 24096 KB Partially correct
17 Correct 411 ms 24048 KB Output is correct
18 Partially correct 283 ms 24236 KB Partially correct
19 Partially correct 357 ms 24220 KB Partially correct
20 Partially correct 327 ms 24096 KB Partially correct
21 Correct 66 ms 23936 KB Output is correct
22 Partially correct 75 ms 24184 KB Partially correct
23 Partially correct 106 ms 24164 KB Partially correct
24 Correct 15 ms 24080 KB Output is correct
25 Correct 15 ms 24144 KB Output is correct
26 Correct 13 ms 24080 KB Output is correct
27 Correct 14 ms 24076 KB Output is correct
28 Correct 11 ms 24080 KB Output is correct
29 Correct 473 ms 24036 KB Output is correct
30 Correct 276 ms 23968 KB Output is correct
31 Correct 489 ms 23980 KB Output is correct
32 Correct 340 ms 24100 KB Output is correct
33 Correct 496 ms 24040 KB Output is correct
34 Partially correct 250 ms 24164 KB Partially correct
35 Partially correct 302 ms 24212 KB Partially correct
36 Partially correct 459 ms 24192 KB Partially correct
37 Partially correct 462 ms 24164 KB Partially correct
38 Partially correct 345 ms 24232 KB Partially correct
39 Partially correct 363 ms 24216 KB Partially correct
40 Partially correct 340 ms 24224 KB Partially correct
41 Partially correct 338 ms 24224 KB Partially correct
42 Partially correct 48 ms 24188 KB Partially correct
43 Partially correct 93 ms 24096 KB Partially correct
44 Partially correct 100 ms 24096 KB Partially correct
45 Partially correct 120 ms 24096 KB Partially correct
46 Partially correct 272 ms 24040 KB Partially correct
47 Partially correct 226 ms 24100 KB Partially correct
48 Partially correct 66 ms 24224 KB Partially correct
49 Partially correct 52 ms 24268 KB Partially correct