제출 #538039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
538039		TaylorSwiftFangirl	Speedrun (RMI21_speedrun)	C++17	0 / 100	3545 ms	4084 KiB

speedrun

#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;

/*
static map<int, map<int, bool>> mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int>> neighbours;

void setHintLen(int l) {
    if (length_set) {
        cerr << "Cannot call setHintLen twice" << endl;
        exit(0);
    }
    length = l;
    length_set = true;
}

void setHint(int i, int j, bool b) {
    if (!length_set) {
        cerr << "Must call setHintLen before setHint" << endl;
        exit(0);
    }
    mp[i][j] = b;
}

int getLength() { return length; }

bool getHint(int j) { return mp[current_node][j]; }

bool goTo(int x) {
    if (neighbours[current_node].find(x) == end(neighbours[current_node])) {
        ++queries;
        return false;
    } else {
        viz.insert(current_node = x);
        return true;
    }
}


*/



int read(int place) {
	int ans = 0;
	for(int i=0; i<10; i++) {
		ans*=2;
		ans += getHint(place*10+i+1);
	}
	return ans;
}

void write(int x, int place, int v) {
	for(int i=0; i<10; i++) {
		setHint(x, place*10+i+1, v&(1<<(9-i)));
	}
}

vector<int> adj[1004], unreached;
void dfs(int x, int p) {
	write(x, 0, p);
	int counter = 0;
	for(auto i : adj[x]) {
		if(i==p) continue;
		if(counter==0) write(x, 1, i);
		else unreached.push_back(i);
		dfs(x, i);
		counter++;
	}
	if(adj[x].size()==1 && unreached.size()>0) {
		write(x, 1, unreached.back());
		unreached.pop_back();
	}
}

void assignHints(int st, int n, int a[], int b[]) {
	setHintLen(20);
	for(int i=1; i<n; i++) {
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
	}
	/*
	for(int i=1; i<=n; i++) {
		cout << i << ": ";
		for(auto j : adj[i]) cout << j << ' ';
		cout << '\n';
	}
	*/
	dfs(1, 0);
	/*
	cout << '\n';
	for(int i=1; i<=n; i++) {
		current_node = i;
		cout << read(0) << ' ' << read(1) << '\n';
	}
	cout << '\n';
	*/
}


void speedrun(int st, int n, int start) {
	int curr = start;
	while(curr != 1) {
		int par = read(0);
		goTo(par);
		curr = par;
		//cout << "p " << curr << '\n';
	}
	
	vector<int> depth{1};
	while(true) {
		int child = read(1);
		if(child == 0) break;
		if(goTo(child)) {
			depth.push_back(child);
			//cout << child << '\n';
		}
		else {
			while(true){
				depth.pop_back();
				goTo(depth.back());
				//cout << "b " << depth.back() << ' ' << current_node << ' '<< child << '\n';
				if(goTo(child)) {
					depth.push_back(child);
					break;
				}
			} 
		}
	}
}
	

/*


int main() {
    int N;
    cin >> N;

    int a[N], b[N];
    for (int i = 1; i < N; ++i) {
        cin >> a[i] >> b[i];
        neighbours[a[i]].insert(b[i]);
        neighbours[b[i]].insert(a[i]);
    }

    assignHints(1, N, a, b);

    if (!length_set) {
        cerr << "Must call setHintLen at least once" << endl;
        exit(0);
    }

    cin >> current_node;
    viz.insert(current_node);

    speedrun(1, N, current_node);

    if ((int)viz.size() < N) {
        cerr << "Haven't seen all nodes" << endl;
        exit(0);
    }

    cerr << "OK; " << queries << " incorrect goto's" << endl;
    return 0;
}
*/

/*
10
1 2
2 3
3 4
4 5
3 7
2 6
1 9
9 8
9 10
*/

• Subtask 1: 0 / 21
• Subtask 2: 0 / 8
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40