oj.uz

Submission #505075

# Submission time Handle Problem Language Result Execution time Memory
505075 2022-01-10T13:01:33 Z duchung Speedrun (RMI21_speedrun) C++17
100 / 100
 274 ms 1036 KB 
#include<bits/stdc++.h>

#include "speedrun.h"
using namespace std;

const int N = 1005;

int timer = 0;
vector<int> edge[N];
int parent[N] , tin[N] , Euler[N];

void dfs(int u)
{
	tin[u] = ++timer;
	Euler[timer] = u;
	for (int v : edge[u])
	{
		if (v == parent[u]) continue;
		parent[v] = u;
		dfs(v);
	}
}

void assignHints (int subtask , int n , int eu[] , int ev[])
{
	for (int i = 1 ; i < n ; ++i)
	{
		edge[eu[i]].push_back(ev[i]);
		edge[ev[i]].push_back(eu[i]);
	}
	dfs(1);

	setHintLen(20);

	for (int u = 1 ; u <= n ; ++u)
	{
		int v;

		if (u != 1)
		{
			v = parent[u];
			for (int j = 0 ; j < 10 ; ++j) setHint(u , j + 1 , v >> j & 1);
		}

		if (tin[u] == n) v = 1;
		else v = Euler[tin[u] + 1];
		for (int j = 0 ; j < 10 ; ++j) setHint(u , j + 11 , v >> j & 1);
	}
}

pair<int , int> Hint[N];
bool visited[N];

void get_val(int cur)
{
    for (int j = 0 ; j < 20 ; ++j) cerr << getHint(j + 1) << " ";
    cerr << "\n";

	for (int j = 0 ; j < 10 ; ++j) if (getHint(j + 1)) Hint[cur].first |= 1 << j;
	for (int j = 10 ; j < 20 ; ++j) if (getHint(j + 1)) Hint[cur].second |= 1 << (j - 10);
}

void speedrun(int subtask , int n , int cur)
{
	int l = getLength();

	if (!visited[cur])
    {
        get_val(cur);
        visited[cur] = true;
    }

	int cnt = 1;
	while(cnt < n)
	{
	    if (!visited[cur])
        {
            get_val(cur);
            visited[cur] = true;
        }

		// cerr << current_node << " " << cur << " " << Hint[cur].first << " " << Hint[cur].second << "\n";

		if (tin[cur] == n)
		{
			while(cur != 1)
			{
				if (!visited[cur])
                {
                    get_val(cur);
                    visited[cur] = true;
                }

                // cerr << current_node << " " << cur << " " << Hint[cur].first << " " << Hint[cur].second << "\n";

				goTo(Hint[cur].first);
				cur = Hint[cur].first;
			}
		}
		else
		{
			int tmp = Hint[cur].second;
			while (!goTo(tmp))
			{
			    if (!visited[cur])
                {
                    get_val(cur);
                    visited[cur] = true;
                }

                // cerr << current_node << " " << cur << " " << Hint[cur].first << " " << Hint[cur].second << "\n";

				goTo(Hint[cur].first);
				cur = Hint[cur].first;
			}
			cur = tmp;
		}

		++cnt;
	}
}

Compilation message

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:65:6: warning: unused variable 'l' [-Wunused-variable]
   65 |  int l = getLength();
      |      ^

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 848 KB Output is correct
2 Correct 217 ms 752 KB Output is correct
3 Correct 274 ms 736 KB Output is correct
4 Correct 211 ms 712 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 784 KB Output is correct
2 Correct 247 ms 724 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 796 KB Output is correct
2 Correct 247 ms 716 KB Output is correct
3 Correct 269 ms 788 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 676 KB Output is correct
2 Correct 236 ms 660 KB Output is correct
3 Correct 250 ms 1036 KB Output is correct
4 Correct 251 ms 660 KB Output is correct
5 Correct 229 ms 704 KB Output is correct
6 Correct 224 ms 788 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 824 KB Output is correct
2 Correct 260 ms 660 KB Output is correct
3 Correct 266 ms 808 KB Output is correct
4 Correct 259 ms 676 KB Output is correct
5 Correct 203 ms 784 KB Output is correct
6 Correct 236 ms 792 KB Output is correct
7 Correct 244 ms 752 KB Output is correct