oj.uz

Submission #647021

# Submission time Handle Problem Language Result Execution time Memory
647021 2022-10-01T11:51:05 Z ksu2009en Speedrun (RMI21_speedrun) C++17
100 / 100
 135 ms 920 KB 
#include "speedrun.h"

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef int ll;

vector<ll>d[1007];

vector<ll>list;

ll parent[1007];

void dfs(ll v, ll par){
    list.push_back(v);
    
    if(par != -1)
        parent[v] = par;
    
    for(auto i: d[v])
        if(i != par)
            dfs(i, v);
}

void assignHints(int subtask, int n, int a[], int b[]) { /* your solution here */
    for(int i = 1; i < n; i++){
        d[a[i]].push_back(b[i]);
        d[b[i]].push_back(a[i]);
    }
    
    ll root = 0;
    for(int i = 1; i <= n; i++)
        if(d[i].size() == 1){
            root = i;
            parent[root] = d[i][0];
            break;
        }
    
    dfs(root, -1);
    
    setHintLen(20);
    
    for(int i = 0; i < list.size(); i++){
        for(int j = 0; j < 10; j++)
            if((parent[list[i]] >> j) % 2 != 0)
                setHint(list[i], j + 1, 1);
        
        ll next = (i + 1 < list.size() ? list[i + 1] : list[0]);
        
        for(int j = 0; j < 10; j++)
            if((next >> j) % 2 != 0)
                setHint(list[i], j + 1 + 10, 1);
    }
}

bool used[1007];

void speedrun(int subtask, int n, int start) { /* your solution here */
    ll visited = 1;
    used[start] = true;
    
    ll go_here = -1, v = start;
    
    while(visited < n){
        //cout << v << endl;
        used[v] = true;
        ll next = 0;
        
        for(int i = 9; i >= 0; i--){
            next *= 2;
            if(getHint(20 - (10 - i - 1)))
                next++;
        }
        
        ll father = 0;
        
        for(int i = 9; i >= 0; i--){
            father *= 2;
            if(getHint(i + 1))
                father++;
        }
        
        //cout << next << ' ' << father << ' ' << go_here<< endl;
        
        if(go_here != -1){
            if(goTo(go_here)){
                v = go_here;
                
                if(!used[go_here])
                    visited++;
                go_here = -1;
            }
            else{
                goTo(father);
                
                v = father;
                
                if(!used[father])
                    visited++;
            }
            continue;
        }
        
        
        if(goTo(next)){
            v = next;
            go_here = -1;
            
            if(!used[next])
                visited++;
            continue;
        }
        
        go_here = next;
        goTo(father);
        
        v = father;
        
        if(!used[father])
            visited++;
    }
    
}

/*
 5
 5
 1 2
 2 3
 3 4
 3 5
 2
 */

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:58:22: 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 < list.size(); i++){
      |                    ~~^~~~~~~~~~~~~
speedrun.cpp:63:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         ll next = (i + 1 < list.size() ? list[i + 1] : list[0]);
      |                    ~~~~~~^~~~~~~~~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 716 KB Output is correct
2 Correct 103 ms 716 KB Output is correct
3 Correct 115 ms 836 KB Output is correct
4 Correct 115 ms 920 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 672 KB Output is correct
2 Correct 104 ms 724 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 672 KB Output is correct
2 Correct 122 ms 724 KB Output is correct
3 Correct 97 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 716 KB Output is correct
2 Correct 88 ms 672 KB Output is correct
3 Correct 131 ms 720 KB Output is correct
4 Correct 115 ms 724 KB Output is correct
5 Correct 135 ms 684 KB Output is correct
6 Correct 112 ms 796 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 716 KB Output is correct
2 Correct 90 ms 732 KB Output is correct
3 Correct 110 ms 792 KB Output is correct
4 Correct 109 ms 716 KB Output is correct
5 Correct 112 ms 720 KB Output is correct
6 Correct 79 ms 728 KB Output is correct
7 Correct 111 ms 672 KB Output is correct