oj.uz

Submission #429324

# Submission time Handle Problem Language Result Execution time Memory
429324 2021-06-15T20:42:42 Z abdzag Stations (IOI20_stations) C++17
21 / 100
 1269 ms 704 KB 
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#include "stations.h"
#define rep(i,a,b) for(int i=int(a);i<int(b);i++)
#define rrep(i,a,b) for(int i=int(a);i>int(b);i--)
#define trav(a,v) for(auto& a: v)
#define sz(v) v.size()
#define all(v) v.begin(),v.end()
#define vi vector<int>

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const long long inf = 2e9;

using namespace std;

vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
	ll counter = 0;
	vector<vector<ll>> g(n);
	rep(i, 0, n - 1) {
		g[u[i]].push_back(v[i]);
		g[v[i]].push_back(u[i]);
	}
	ll cur = 0;
	queue<ll> q;
	rep(i, 0, g.size()) {
		if (g[i].size() == 1)q.push(i);
	}
	vector<int> ans(n);
	vector<bool> visited(n);
	ll counter2 = 0;
	while (!q.empty()) {
		cur = q.front();
		q.pop();
		while (counter < n) {
			visited[cur] = 1;
			ans[cur] = counter2++;
			counter++;
			trav(a, g[cur])if (!visited[a])cur = a;
			if (g[cur].size() > 2) {
				counter2 = ((counter2 / 1000) + 1) * 1000;
				ans[cur] = 1e6;
				break;
			}

		}
	}
	
	return ans;
}

int find_next_station(int s, int t, vector<int> c) {
	int ans;
	if (s == 1e6) {
		trav(a, c) {
			if (a/1000==t/1000)ans = a;
		}
	}
	else if (s/1000!=t/1000) {
		ans = -1;
		trav(a, c)ans = max(a, ans);
	}
	else if (s < t) {
		ans = -1;
		trav(a, c)ans = max(a, ans);
	}
	else {
		ans = 1e7;
		trav(a, c)ans = min(a, ans);
	}
	return ans;
}

Compilation message

stations.cpp: In function 'int find_next_station(int, int, std::vector<int>)':
stations.cpp:73:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |  return ans;
      |         ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 488 KB Output is correct
2 Correct 573 ms 488 KB Output is correct
3 Correct 1269 ms 528 KB Output is correct
4 Correct 811 ms 616 KB Output is correct
5 Correct 609 ms 484 KB Output is correct
6 Correct 474 ms 520 KB Output is correct
7 Correct 505 ms 484 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 280 KB Invalid labels (duplicates values). scenario=0, label=0
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 533 ms 480 KB Output is correct
2 Correct 612 ms 476 KB Output is correct
3 Correct 1126 ms 400 KB Output is correct
4 Correct 781 ms 528 KB Output is correct
5 Correct 719 ms 400 KB Output is correct
6 Correct 583 ms 476 KB Output is correct
7 Correct 467 ms 484 KB Output is correct
8 Correct 3 ms 484 KB Output is correct
9 Correct 3 ms 480 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 781 ms 492 KB Output is correct
12 Correct 570 ms 604 KB Output is correct
13 Correct 789 ms 704 KB Output is correct
14 Correct 518 ms 484 KB Output is correct
15 Correct 82 ms 420 KB Output is correct
16 Correct 58 ms 548 KB Output is correct
17 Correct 117 ms 488 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1069 ms 400 KB Output is correct
2 Correct 865 ms 488 KB Output is correct
3 Correct 769 ms 484 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 6 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 693 ms 488 KB Output is correct
8 Correct 1214 ms 400 KB Output is correct
9 Correct 745 ms 568 KB Output is correct
10 Correct 622 ms 484 KB Output is correct
11 Incorrect 1 ms 200 KB Invalid labels (duplicates values). scenario=5, label=1000000
12 Halted 0 ms 0 KB -

Subtask #5
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 838 ms 680 KB Output is correct
2 Correct 566 ms 512 KB Output is correct
3 Correct 1128 ms 544 KB Output is correct
4 Correct 797 ms 452 KB Output is correct
5 Correct 701 ms 564 KB Output is correct
6 Correct 604 ms 528 KB Output is correct
7 Correct 429 ms 484 KB Output is correct
8 Correct 3 ms 476 KB Output is correct
9 Correct 4 ms 472 KB Output is correct
10 Correct 2 ms 476 KB Output is correct
11 Incorrect 5 ms 376 KB Invalid labels (duplicates values). scenario=0, label=0
12 Halted 0 ms 0 KB -