oj.uz

Submission #647008

# Submission time Handle Problem Language Result Execution time Memory
647008 2022-10-01T11:06:33 Z ksu2009en Speedrun (RMI21_speedrun) C++17
33 / 100
 255 ms 844 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 long long ll;


vector<ll>d[1007];

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]);
    }
    
    setHintLen(316);
    
    int sz = sqrt(n);
    
    for(int i = 1; i <= n; i++){
        if(d[i].size() <= sz){ // the degree is less/equal than sqrt(n) => we can build an adjestancy list (10 bits per vertex)
            int pos = 1;
            
            for(auto x: d[i]){
                for(int j = pos; j <= pos + 9; j++){
                    if((x >> (j - pos)) % 2 != 0)
                        setHint(i, j, 1);
                }
                pos += 10;
            }
        }
        // else: leave it as it is, we're gonna check all N nodes using goTo later in speedrun
    }
}

bool used[1007];

void dfs(ll v, ll par, int &n){
    used[v] = true;
    bool ok = false;
    
    for(int i = 1; i <= 316; i++){
        if(getHint(i))
            ok = true;
    }
    
    if(!ok){ // there are no set bits, thus this node has degree > sqrt(n) and we can traverse over all N nodes using goTo (the amount of such nodes will not exceed sqrt(N) - why? idk, just seems logical, search for proof)
        
        for(int i = 1; i <= n; i++){
            if(goTo(i))
                dfs(i, v, n);
        }
    }
    else{ // this node has its adjactency list
        for(int i = 1; i + 9 <= 316; i += 10){ // the start of new code
            ll v2 = 0;
            for(int j = 9; j >= 0; j--){
                v2 *= 2;
                
                if(getHint(i + j))
                    v2++;
            }
            
            if(v2 == 0) // there is an end in the list!
                break;
            
            if(!used[v2]){
                goTo(v2);
                dfs(v2, v, n);
            }
        }
    }
    
    if(par != -1) // go back, from where we've come
        goTo(par);
}

void speedrun(int subtask, int n, int start) { /* your solution here */
    dfs(start, -1, n);
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:37:24: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         if(d[i].size() <= sz){ // the degree is less/equal than sqrt(n) => we can build an adjestancy list (10 bits per vertex)
      |            ~~~~~~~~~~~~^~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 704 KB Output is correct
2 Correct 55 ms 676 KB Output is correct
3 Correct 64 ms 672 KB Output is correct
4 Correct 94 ms 716 KB Output is correct

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB The length is too large
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 720 KB Output is correct
2 Correct 129 ms 712 KB Output is correct
3 Correct 255 ms 844 KB Output is correct
4 Correct 93 ms 752 KB Output is correct
5 Correct 101 ms 672 KB Output is correct
6 Correct 70 ms 672 KB Output is correct

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB The length is too large
2 Halted 0 ms 0 KB -