oj.uz

Submission #500901

# Submission time Handle Problem Language Result Execution time Memory
500901 2022-01-01T15:50:35 Z keta_tsimakuridze Speedrun (RMI21_speedrun) C++14
100 / 100
 141 ms 888 KB 
#include "speedrun.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, f[N], cnt, deg[N], l[N] ;
vector<int> V[N];
vector<int> x;
/*
#include <iostream>
#include <map>
#include <set>
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) == neighbours[current_node].end()) {
        ++queries;
        return false;
    } else {
        viz.insert(current_node = x);
        cout << current_node <<" is current" << endl;
        return true;
    }
} */
void dfs(int u,int p) {
	for(int i = 1; i <= 10; i++) {
		if(p & (1 << (i - 1))) setHint(u, i, 1);
	}
	x.push_back(u);
	for(int i = 0; i < V[u].size(); i++) {
		if(V[u][i] == p) continue;
		dfs(V[u][i], u);
	}
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	setHintLen(20);
	for(int i = 1; i < N; i++) {
		V[A[i]].push_back(B[i]);
		V[B[i]].push_back(A[i]);
	}
	dfs(1, 0);
	x.push_back(1);
	for(int i = 0; i + 1 < x.size(); i++) {
		for(int j = 11; j <= 20; j++) {
			if(x[i + 1] & (1 << (j - 11))) setHint(x[i], j, 1);
		}
	}
}
void speedrun(int subtask, int N, int start) { /* your solution here */
	
	n = N;
	int cnt = 0;
	int w = 0, st = start;
	while(n--) {
		cnt++;
		int x = 0;
		for(int j = 11; j <= 20; j++) {
			x += getHint(j) * (1 << (j - 11));
		}
		while(!goTo(x)) { w++; assert(st != 1 || w <= n);
			int p = 0;
			for(int j = 1; j <= 10; j++) {
				p += getHint(j) * (1 << (j - 1));
			}
			goTo(p); start = p;
		}
		start = x;
	}
}
/*
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(4, N, a, b);

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

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

    speedrun(4, N, current_node);

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

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

Compilation message

speedrun.cpp: In function 'void dfs(int, int)':
speedrun.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for(int i = 0; i + 1 < x.size(); i++) {
      |                 ~~~~~~^~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 788 KB Output is correct
2 Correct 77 ms 756 KB Output is correct
3 Correct 124 ms 700 KB Output is correct
4 Correct 98 ms 784 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 732 KB Output is correct
2 Correct 96 ms 748 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 888 KB Output is correct
2 Correct 114 ms 776 KB Output is correct
3 Correct 68 ms 744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 728 KB Output is correct
2 Correct 141 ms 676 KB Output is correct
3 Correct 75 ms 716 KB Output is correct
4 Correct 107 ms 732 KB Output is correct
5 Correct 141 ms 720 KB Output is correct
6 Correct 114 ms 844 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 752 KB Output is correct
2 Correct 127 ms 744 KB Output is correct
3 Correct 98 ms 732 KB Output is correct
4 Correct 116 ms 752 KB Output is correct
5 Correct 80 ms 872 KB Output is correct
6 Correct 112 ms 768 KB Output is correct
7 Correct 103 ms 736 KB Output is correct