— Dark mode

NOI 2019

Distance Code

  • Start: 2019-03-06 11:00:00
  • End: 2019-03-06 16:00:00
CSES - NOI 2019 - Results
Submission details
Task:Distance Code
Sender:Loke Gustafsson
Submission time:2019-03-07 00:57:22 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED21
#2ACCEPTED47
#3ACCEPTED32
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.02 s1, 2, 3details
#3ACCEPTED0.02 s1, 2, 3details
#4ACCEPTED0.02 s1, 2, 3details
#5ACCEPTED0.02 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.02 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.02 s1, 2, 3details
#11ACCEPTED0.02 s1, 2, 3details
#12ACCEPTED0.03 s2, 3details
#13ACCEPTED0.01 s2, 3details
#14ACCEPTED0.01 s2, 3details
#15ACCEPTED0.02 s2, 3details
#16ACCEPTED0.15 s3details
#17ACCEPTED0.16 s3details
#18ACCEPTED0.15 s3details
#19ACCEPTED0.16 s3details
#20ACCEPTED0.02 s1, 2, 3details

Compiler report

input/code.cpp: In member function 'bool Node::isLeaf()':
input/code.cpp:41:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   return (nextChild >= children.size() || children.size() == 0);
           ~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Code

#include <iostream>
#include <vector>
#include <unordered_map>

#define ll long long
#define vi vector<ll>
#define adjList unordered_map<ll, vi>

using namespace std;

struct Node
{
	Node* parent;
	vector<Node*> children;
	ll id;
	ll nextChild;

	Node(ll i, Node* par)
	{
		this->id = i;
		this->parent = par;
		this->nextChild = 0;
	}

	static Node* makeNode(ll i, Node* par, adjList& graph) // creates rooted graph from adjList
	{
		Node* n = new Node(i, par);
		for (ll p : graph[i])
		{
			if (par != nullptr && p == par->id)
			{
				continue;
			}
			n->children.push_back(makeNode(p, n, graph));
		}
		return n;
	}

	bool isLeaf()
	{
		return (nextChild >= children.size() || children.size() == 0);
	}

	Node* next()
	{
		if ( isLeaf() )
		{
			return parent;
		}
		else
		{
			return children[nextChild++];
		}
	}
};

void printEdges(Node* active)
{
	for (Node* child : active->children)
	{
		cout << child->id << " " << active->id << endl;
		printEdges(child);
	}

}

int main()
{
	ll t;
	cin >> t;
	ll n;
	cin >> n;

	if (t == 1)
	{
		// encode
		adjList graph;
		for (int i = 0; i < n - 1; i++)
		{
			ll a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		Node* active = Node::makeNode(1, nullptr, graph);

		while ( !( active->isLeaf() ) ) 
		{
			active = active->next();
		}
		// traverse tree and destroy nodes
		for (int i = 0; i < n; i++)
		{
			cout << active->id << " ";

			active = active->next();
			if (active == nullptr)
			{
				break;
			}
			
			while (!(active->isLeaf()))
			{
				active = active->next();
			}
		}
		cout << endl;
	}
	else
	{
		// decode
		ll idn = 0;
		Node* active = new Node(++idn, nullptr);

		for (int i = 0; i < n - 1; i++)
		{
			ll j;
			cin >> j;
			
			if (active->parent == nullptr)
			{
				active->parent = new Node(++idn, nullptr);
				active->parent->children.push_back(active);
			}
			active = active->parent;
			
			while (j > 1)
			{
				Node* child = new Node(++idn, active);
				active->children.push_back(child);
				active = child;
				--j;
			}
		}

		printEdges(active);
	}

    return 0;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
2
2 1
view save

correct output
(empty)

user output
1 2
view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
1
3
3 1
2 1
view save

correct output
(empty)

user output
1 2
3 2
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
2 3
1 2
4 3
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
2 4
1 2
3 2
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
2 3
1 2
4 3
5 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
1 2
3 2
4 3
5 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
2 5
1 2
3 2
4 2
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
2 10
1 2
3 2
4 2
5 2
...
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
6 7
5 6
4 5
3 4
2 3
...
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
1 2
3 2
4 3
5 2
6 5
...
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
5 6
4 5
3 4
2 3
1 2
...
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
2 500
1 2
3 2
4 2
5 2
...
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
350 351
349 350
348 349
347 348
346 347
...
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
1 2
3 2
4 3
5 4
6 4
...
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
6 7
5 6
4 5
3 4
2 3
...
view save

Test 16

Group: 3

Verdict: ACCEPTED

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

correct output
(empty)

user output
2 100000
1 2
3 2
4 2
5 2
...
view save

Test 17

Group: 3

Verdict: ACCEPTED

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

correct output
(empty)

user output
34232 34233
34231 34232
34230 34231
34229 34230
34228 34229
...
view save

Test 18

Group: 3

Verdict: ACCEPTED

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

correct output
(empty)

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

Test 19

Group: 3

Verdict: ACCEPTED

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

correct output
(empty)

user output
99999 100000
99998 99999
99997 99998
99983 99997
99982 99983
...
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 6
2 4
1 2
3 2
5 4
view save

Tasks

A Distance Code-B Thieves and Prisons-C Graph Ordering-

Submissions (Loke Gustafsson)

2019-03-07 00:57:22 1002019-03-06 15:42:25 68