oj.uz

Submission #700012

# Submission time Handle Problem Language Result Execution time Memory
700012 2023-02-18T12:43:29 Z Nursik Speedrun (RMI21_speedrun) C++14
100 / 100
 120 ms 920 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 672 KB Output is correct
2 Correct 117 ms 872 KB Output is correct
3 Correct 106 ms 756 KB Output is correct
4 Correct 120 ms 672 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 744 KB Output is correct
2 Correct 68 ms 832 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 800 KB Output is correct
2 Correct 108 ms 868 KB Output is correct
3 Correct 98 ms 800 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 816 KB Output is correct
2 Correct 97 ms 720 KB Output is correct
3 Correct 76 ms 700 KB Output is correct
4 Correct 88 ms 748 KB Output is correct
5 Correct 99 ms 832 KB Output is correct
6 Correct 70 ms 684 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 728 KB Output is correct
2 Correct 103 ms 736 KB Output is correct
3 Correct 104 ms 760 KB Output is correct
4 Correct 100 ms 696 KB Output is correct
5 Correct 91 ms 684 KB Output is correct
6 Correct 93 ms 736 KB Output is correct
7 Correct 97 ms 920 KB Output is correct