oj.uz

Submission #593971

# Submission time Handle Problem Language Result Execution time Memory
593971 2022-07-11T18:33:52 Z Clan328 Stations (IOI20_stations) C++17
10 / 100
 882 ms 560 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define nL '\n'
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll MOD = 1e9 + 7;

void settings()__attribute__((constructor));

void eval(bool condition) { cout << (condition ? "yes" : "no") << nL; }
void Eval(bool condition) { cout << (condition ? "Yes" : "No") << nL; }
// void EVAL(bool condition) { cout << (condition ? "YES" : "NO") << nL; }

int ipow(int a, int n) {
   if (n == 0) return 1;
   int x = ipow(a, n/2);
   if (n % 2 == 0) return x*x;
   return x*x*a;
}

template <typename T>
ostream& operator<<(ostream& stream, const vector<T>& v) {
	for (auto elem : v) 
		stream << elem << " ";
	return stream;
}

template <typename T>
istream& operator>>(istream& stream, vector<T>& v){
   for(auto &elem : v)
		stream >> elem;
   return stream;
}

void settings() {
	#ifdef LOCAL
		freopen("io/input.txt", "r", stdin);
		freopen("io/output.txt", "w", stdout);
	#endif

	ios::sync_with_stdio(0);
	cin.tie(0);
}

int tmpD;
vi visited, res;
vvi G;

void dfs(int v, int val) {
	visited[v] = true;
	res[v] = val;
	int idx = 1;
	for (auto u : G[v]) {
		if (visited[u]) continue;
		dfs(u, val*tmpD+idx);
		idx++;
	}
}

vi label(int n, int k, std::vector<int> u, std::vector<int> v) {
	res = vi(n);
	vi deg(n);
	G = vvi(n);
	visited = vi(n);
	for (int i = 0; i < u.size(); i++) {
		G[u[i]].pb(v[i]);
		G[v[i]].pb(u[i]);
		deg[u[i]]++;
		deg[v[i]]++;
	}

	int maxDeg = 0;
	for (int i = 1; i < n; i++) if (deg[i] > deg[maxDeg]) maxDeg = i;

	int x = -1;
	// for (int i = 0; i < n; i++) {
	// 	if (deg[i] < deg[maxDeg]) {
	// 		if (x == -1) x = i;
	// 		else if (deg[x] < deg[i]) x = i;
	// 	}
	// }

	// if (x == -1) x = 0;
	
	x = maxDeg;
	tmpD = deg[x];
	dfs(x, 0);
	// cout << res << nL;
	return res;
}

int find_next_station(int s, int t, std::vector<int> c) {
	if (c.size() == 1) return c[0];

	int d;
	// cout << s << nL;
	if (s == 0) d = c[c.size()-1];
	else d = (c[1]-1)/s;

	if (d == 0) return -1;
	while (t > s) {
		if ((t-1)/d == s) return t;
		t = (t-1)/d;
	}
	return (s-1)/d;
}

Compilation message

stations.cpp: In function 'vi label(int, int, std::vector<int>, std::vector<int>)':
stations.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |  for (int i = 0; i < u.size(); i++) {
      |                  ~~^~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 16.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 532 KB Output is correct
2 Correct 616 ms 444 KB Output is correct
3 Correct 514 ms 504 KB Output is correct
4 Correct 1 ms 500 KB Output is correct
5 Correct 4 ms 496 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 553 ms 420 KB Output is correct
8 Correct 882 ms 416 KB Output is correct
9 Correct 671 ms 416 KB Output is correct
10 Correct 573 ms 416 KB Output is correct
11 Correct 5 ms 500 KB Output is correct
12 Correct 4 ms 492 KB Output is correct
13 Correct 3 ms 500 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 1 ms 496 KB Output is correct
16 Correct 449 ms 416 KB Output is correct
17 Correct 466 ms 416 KB Output is correct
18 Correct 505 ms 420 KB Output is correct
19 Correct 474 ms 416 KB Output is correct
20 Correct 494 ms 416 KB Output is correct

Subtask #5
0 / 61.0

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