Submission #700012

#	Time	Username	Problem	Language	Result	Execution time	Memory
700012		Nursik	Speedrun (RMI21_speedrun)	C++14	100 / 100	120 ms	920 KiB

speedrun

#include "speedrun.h"
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
 
using namespace std;
#define pb push_back

int used[2000];
int father[2000];
vector<int> pt, g[2000];
void dfs(int v = 1, int p = 0){
    pt.pb(v);
    for (auto to : g[v]){
        if (to != p){
            father[to] = v;
            dfs(to, v);
        }
    }
}
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    for (int i = 1; i < N; ++i){
        int x = A[i], y = B[i];
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs();
    for (int i = 0; i < N; ++i){
        int v = pt[i];
        for (int j = 0; j < 10; ++j){
            if ((1 << j) & father[v]){
                setHint(v, j + 1, 1);
            }
        }
        if (i + 1 < N){
            for (int j = 0; j < 10; ++j){
                if ((1 << j) & pt[i + 1]){
                    setHint(v, j + 10 + 1, 1);
                }
            }
        }
    }
}
int get1(){
    int x = 0;
    for (int i = 0; i < 10; ++i){
        x += (1 << i) * getHint(i + 1);
    }
    return x;
}
int get2(){
    int x = 0;
    for (int i = 0; i < 10; ++i){
        x += (1 << i) * getHint(i + 11);
    }
    return x;
}
void speedrun(int subtask, int N, int start) { /* your solution here */
    int kol = 1;
    used[start] = 1;
    while (start != 1){
        int y = get1();
        goTo(y);
        kol += (used[y] == 0);
        used[y] = 1;
        start = y;
    }
   // cout << kol << '\n';
    int go = get2();
    while (kol != N){
      //  cout << kol << " " << go << '\n';
        if (!goTo(go)){
        //    cout << "kek\n";
            goTo(get1());
        }
        else{
            kol += (used[go] == 0);
            if (kol == N){
                break;
            }
            used[go] = 1;
            go = get2();
        }
    }
}

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