Code Submission Evaluation System Login

NOI 2019 Open

Start:N/A
End:N/A
 

Tasks | Scoreboard | Statistics


CSES - NOI 2019 Open - Results
History
0:42:43100
0:33:240
Task:Distance Code
Sender:tmk
Submission time:2019-03-10 10:46:07
Language:C++
Status:READY
Score:100

Feedback

groupverdictscore
#1ACCEPTED21
#2ACCEPTED47
#3ACCEPTED32

Test results

testverdicttime (s)group
#1ACCEPTED0.03 / 1.001, 2, 3details
#2ACCEPTED0.04 / 1.001, 2, 3details
#3ACCEPTED0.02 / 1.001, 2, 3details
#4ACCEPTED0.04 / 1.001, 2, 3details
#5ACCEPTED0.03 / 1.001, 2, 3details
#6ACCEPTED0.03 / 1.001, 2, 3details
#7ACCEPTED0.02 / 1.001, 2, 3details
#8ACCEPTED0.04 / 1.001, 2, 3details
#9ACCEPTED0.04 / 1.001, 2, 3details
#10ACCEPTED0.02 / 1.001, 2, 3details
#11ACCEPTED0.03 / 1.001, 2, 3details
#12ACCEPTED0.03 / 1.002, 3details
#13ACCEPTED0.03 / 1.002, 3details
#14ACCEPTED0.03 / 1.002, 3details
#15ACCEPTED0.03 / 1.002, 3details
#16ACCEPTED0.05 / 1.003details
#17ACCEPTED0.05 / 1.003details
#18ACCEPTED0.04 / 1.003details
#19ACCEPTED0.06 / 1.003details
#20ACCEPTED0.03 / 1.001, 2, 3details

Code

#include<bits/stdc++.h>
using namespace std;
#ifndef d
#define d(...)
#endif
#define st first
#define nd second
#define pb push_back
#define siz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
typedef long long LL;
typedef long double LD;
constexpr int INF=1e9+7;
constexpr LL INFL=1e18;
template<class L, class R> ostream &operator<<(ostream &os, pair<L,R> P) {
  return os << "(" << P.st << "," << P.nd << ")";
}
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag,
         tree_order_statistics_node_update>;
*/

constexpr int maxn = 100005;

int n;
vector<int> G[maxn], preord;

void dfs(int a, int par=-1) {
	preord.push_back(a);
	for(auto v:G[a])
		if(v != par)
			dfs(v, a);
}

void encode() {
	cin >> n;
	for(int i=0; i<n-1; i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}
	
	dfs(1);
	reverse(all(preord));
	for(auto x:preord)
		cout << x << " ";
	cout << "\n";
}

vector<int> buck[3*maxn];
vector<pair<int, int>> edges;

void decode() {
	cin >> n;
	int lst = n;
	int pos = maxn;
	for(int i=1; i<n; i++) {
		int dist;
		cin >> dist;
		if(dist == 1) {
			edges.emplace_back(lst, n-i);
			pos--;
			while(not buck[pos].empty()) {
				auto w = buck[pos].back();
				buck[pos].pop_back();
				edges.emplace_back(n-i, w);
			}
			lst = n-i;
		} else {
			//cerr << "lst () laduje do: " << lst << " -> " << pos << endl;
			buck[--pos].push_back(lst);
			pos += dist - 1;
			lst = n-i;
		}
	}
	
	for(auto& e:edges)
		cout << e.st << " " << e.nd << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	if(T == 1) encode();
	else decode();
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
2
2 1

view   save

correct output
(empty)

user output
2 1

view   save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
3
3 1
2 1

view   save

correct output
(empty)

user output
2 1
1 3

view   save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
4
3 2
2 1
4 1
view   save

correct output
(empty)

user output
3 2
2 1
1 4

view   save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
4
2 3
3 4
1 3
view   save

correct output
(empty)

user output
3 2
2 4
2 1

view   save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
5
3 5
4 1
1 3
...
view   save

correct output
(empty)

user output
5 4
3 2
2 1
1 4

view   save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
5
3 2
3 4
5 1
...
view   save

correct output
(empty)

user output
4 3
3 5
2 1
1 3

view   save

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
5
4 3
1 4
4 2
...
view   save

correct output
(empty)

user output
3 2
2 4
2 5
2 1

view   save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
10
9 3
8 9
2 9
...
view   save

correct output
(empty)

user output
3 2
2 4
2 5
2 6
2 7
...
view   save

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
10
9 2
5 8
7 1
...
view   save

correct output
(empty)

user output
10 9
9 8
7 6
6 5
5 4
...
view   save

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
10
10 4
9 1
4 7
...
view   save

correct output
(empty)

user output
10 9
9 8
8 7
6 5
5 7
...
view   save

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
10
2 6
4 3
3 5
...
view   save

correct output
(empty)

user output
9 8
8 7
7 10
6 5
5 4
...
view   save

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
1
500
10 6
6 255
6 428
...
view   save

correct output
(empty)

user output
3 2
2 4
2 5
2 6
2 7
...
view   save

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
1
500
152 466
451 313
158 479
...
view   save

correct output
(empty)

user output
500 499
499 498
498 497
497 496
496 495
...
view   save

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
1
500
109 440
330 190
443 161
...
view   save

correct output
(empty)

user output
500 499
499 498
498 497
497 496
492 491
...
view   save

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
1
500
144 373
257 233
341 318
...
view   save

correct output
(empty)

user output
500 499
499 498
498 497
497 496
496 495
...
view   save

Test 16

Group: 3

Verdict: ACCEPTED

input
1
100000
54983 75172
93807 75172
44082 75172
...
view   save

correct output
(empty)

user output
3 2
2 4
2 5
2 6
2 7
...
view   save

Test 17

Group: 3

Verdict: ACCEPTED

input
1
100000
88863 19059
86423 76688
98536 95984
...
view   save

correct output
(empty)

user output
100000 99999
99999 99998
99998 99997
99997 99996
99996 99995
...
view   save

Test 18

Group: 3

Verdict: ACCEPTED

input
1
100000
59979 6389
19097 24999
27846 82330
...
view   save

correct output
(empty)

user output
100000 99999
99998 99997
99996 99995
99995 99994
99993 99992
...
view   save

Test 19

Group: 3

Verdict: ACCEPTED

input
1
100000
58761 66001
25102 51081
98625 67861
...
view   save

correct output
(empty)

user output
100000 99999
99999 99998
99998 99997
99997 99996
99996 99995
...
view   save

Test 20

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
6
2 1
3 2
4 2
...
view   save

correct output
(empty)

user output
4 3
3 5
3 2
2 6
2 1
view   save