oj.uz

Submission #871571

# Submission time Handle Problem Language Result Execution time Memory
871571 2023-11-11T06:12:51 Z TAhmed33 Speedrun (RMI21_speedrun) C++17
60 / 100
 194 ms 1728 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;
const int m = 31;
vector <int> conv (int x) {
	vector <int> ret;
	for (int i = 9; i >= 0; i--) {
		ret.push_back((x >> i) & 1);
	}
	return ret;
}
void assignHints (int subtask, int n, int a[], int b[]) {
    if (subtask == 2) {
        int deg[n + 1] = {};
        if (n == 1) return;
        for (int i = 1; i < n; i++) {
            deg[a[i]]++;
            deg[b[i]]++;
        }
        int pos = 1;
        for (int i = 1; i <= n; i++) {
            if (deg[i] > 1) {
                pos = i;
            }
        }
        setHintLen(1);
        setHint(pos, 1, 1);
        return;
    }
    if (subtask == 3) {
        vector <int> adj[n + 1];
        for (int i = 1; i < n; i++) {
            adj[a[i]].push_back(b[i]);
            adj[b[i]].push_back(a[i]);
        }
        setHintLen(20);
        for (int i = 1; i <= n; i++) {
            auto d = conv(adj[i][0]);
            for (int l = 1; l <= 10; l++) {
                setHint(i, l, d[l - 1]);
            }
            if (adj[i].size() == 1) continue;
            d = conv(adj[i][1]);
            for (int l = 1; l <= 10; l++) {
                setHint(i, l + 10, d[l - 1]);
            }
        }
        return;
    }
	vector <int> adj[n + 1];
	for (int i = 1; i < n; i++) {
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
	}
	setHintLen(316);
	for (int i = 1; i <= n; i++) {
		if (adj[i].size() > m) continue;
		setHint(i, 316, 1);
		for (int j = 0; j < (int)adj[i].size(); j++) {
			auto x = conv(adj[i][j]);
			for (int l = 10 * j + 1; l <= 10 * j + 10; l++) {
				setHint(i, l, x[l - 10 * j - 1]);
			}	
		}
	}
}
int n;
void dfs (int pos, int par) {
	if (getHint(316) == 1) {
		vector <int> adj;
		for (int j = 0; j <= 30; j++) {
			int x = 0;
			for (int l = 10 * j + 1; l <= 10 * j + 10; l++) {
				x *= 2; x += getHint(l);
			}
			if (x != 0 && x != par) {
				adj.push_back(x);
			}
		}
		for (auto i : adj) {
			goTo(i);
			dfs(i, pos);
			goTo(pos);
		}
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (i == pos || i == par) continue;
		if (goTo(i)) {
			dfs(i, pos);
			goTo(pos);
		}
	}
}
void dfs2 (int pos, int par) {
    int x = 0;
    for (int i = 1; i <= 10; i++) {
        x *= 2; x += getHint(i);
    }
    if (x != 0 && x != par) {
        goTo(x); dfs2(x, pos); goTo(pos);
    }
    x = 0;
    for (int i = 11; i <= 20; i++) {
        x *= 2; x += getHint(i);
    }
    if (x != 0 && x != par) {
        goTo(x); dfs2(x, pos); goTo(pos);
    }
}
void speedrun (int subtask, int N, int start) {
    if (subtask == 2) {
        if (N == 1) return;
        int x = getHint(1);
        if (x == 1) {
            for (int i = 1; i <= N; i++) {
                if (i == start) continue;
                goTo(i); goTo(start);
            }
            return;
        }
        for (int i = 1; i <= N; i++) {
            if (i == start) continue;
            if (goTo(i)) {
                for (int j = 1; j <= N; j++) {
                    if (j == i || j == start) continue;
                    goTo(j); goTo(i);
                }
                goTo(start);
                return;
            }
        }
        return;
    }
    if (subtask == 3) {
        dfs2(start, -1); return;
    }
	n = N; dfs(start, -1);	
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 1196 KB Output is correct
2 Correct 100 ms 940 KB Output is correct
3 Correct 104 ms 1200 KB Output is correct
4 Correct 107 ms 1196 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1540 KB Output is correct
2 Correct 12 ms 1276 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 944 KB Output is correct
2 Correct 104 ms 1452 KB Output is correct
3 Correct 102 ms 1716 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 1196 KB Output is correct
2 Correct 125 ms 940 KB Output is correct
3 Correct 194 ms 1328 KB Output is correct
4 Correct 88 ms 940 KB Output is correct
5 Correct 110 ms 1708 KB Output is correct
6 Correct 59 ms 1728 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB The length is too large
2 Halted 0 ms 0 KB -