oj.uz

Submission #646624

# Submission time Handle Problem Language Result Execution time Memory
646624 2022-09-30T10:39:39 Z ksu2009en Speedrun (RMI21_speedrun) C++17
29 / 100
 45 ms 856 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>

using namespace std;

void assignHints(int subtask, int n, int a[], int b[]) { /* your solution here */
    if(subtask == 1){
        setHintLen(n);
        for(int i = 1; i < n; i++){
            setHint(a[i], b[i], 1);
            setHint(b[i], a[i], 1);
        }
    }
    else if(subtask == 2){
        int center = 0;
        map<int, int> mp;
        for(int i = 1; i < n; i++)
            mp[a[i]]++, mp[b[i]]++;
        
        int mx = 0;
        for(auto i: mp)
            if(i.second > mx){
                mx = i.second;
                center = i.first;
            }
        
        setHintLen(20);

        for(int i = 1; i <= n; i++){
            if(i == center)
                continue;
            
            for(int j = 0; j < 20; j++){
                if((center >> j) % 2 != 0){
                    setHint(i, j + 1, 1);
                }
            }
        }
        
    }
}

bool used[1007];

void dfs(int v, int par, int &n){
    used[v] = true;
    for(int i = 1; i <= n; i++){
        if(!used[i] && getHint(i)){
            goTo(i);
            dfs(i, v, n);
        }
    }
    if(par != -1)
        goTo(par);
}

void speedrun(int subtask, int n, int start) { /* your solution here */
    if(subtask == 1){
        dfs(start, -1, n);
    }
    else if(subtask == 2){
        bool ok = false;
        for(int i = 1; i <= 20; i++)
            if(getHint(i))
                ok = true;
        
        int center = 0;
        if(ok){
            for(int j = 19; j >= 0; j--){
                center *= 2;
                if(getHint(j + 1)){
                    center++;
                }
            }
            
            goTo(center);
        }
        else
            center = start;
        
        
        for(int i = 1; i <= n; i++){
            if(i != start && i != center){
                goTo(i);
                goTo(center);
            }
        }
    }
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 748 KB Output is correct
2 Correct 39 ms 856 KB Output is correct
3 Correct 45 ms 832 KB Output is correct
4 Correct 36 ms 752 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 672 KB Output is correct
2 Correct 38 ms 692 KB Output is correct

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB setHintLen was never called
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB setHintLen was never called
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB setHintLen was never called
2 Halted 0 ms 0 KB -