oj.uz

Submission #770786

# Submission time Handle Problem Language Result Execution time Memory
770786 2023-07-02T00:00:59 Z gg123_pe Speedrun (RMI21_speedrun) C++14
90 / 100
 144 ms 968 KB 
#include "speedrun.h"
#include <bits/stdc++.h> 

using namespace std; 

#define f(i,a,b) for(int i = a; i < b; i++)
const int N = 1005; 

void setHintLen (int l);
void setHint(int i, int j, bool b);
int getLength ();
bool getHint(int j);
bool goTo(int x);

int n; 
int p[N]; 
vector <int> adj[N], curr, order; 
bool vis[N]; 

void dfs(int u, int f){
    curr.push_back(u);
    order.push_back(u); 

    p[u] = f; 

    for(int v: adj[u]){
        if(v == f) continue; 
        dfs(v, u); 
    }
    if(f != 0) curr.push_back(f); 
}
void assign(int node, int pos, int val){
    int l = 10*(pos-1) + 1, r = 10*pos;
    f(i,l,r+1){
        int x = i - l; 
        if(val&(1<<x)) setHint(node, i, 1);
    } 
}
void assignHints(int subtask, int Ni, int A[], int B[]) { 
    n = Ni; 
    f(i,1,n){
        adj[A[i]].push_back(B[i]); 
        adj[B[i]].push_back(A[i]); 
    }

    if(subtask == 2){
        setHintLen(1); 
        f(i,1,n+1){
            if(adj[i].size() == n-1){
                setHint(i, 1, 1); 
                break; 
            }
        }
        return; 
    }
    if(subtask == 3){
        setHintLen(20); 
        int l; 
        f(i,1,n+1){
            if(adj[i].size() == 1){
                l = i; 
                break; 
            }
        }
        dfs(l, 0); 
        f(i,0,n){
            int node = order[i]; 
            if(i > 0) assign(node, 1, order[i-1]); 
            if(i+1 < n) assign(node, 2, order[i+1]); 
        }
        return; 
    }
    setHintLen(30);
    dfs(1, 0); 

    int id = 0; 
    f(i,0,n){
        int node = order[i]; 
        assign(node, 1, p[node]); 
        assign(node, 2, curr[id++]);
        assign(node, 3, curr[id++]);   
    }
}
int get(int pos){
    int ans = 0, l = 10*(pos-1) + 1, r = 10*pos;
    f(i,l,r+1){
        int x = i-l; 
        if(getHint(i)) ans ^= (1<<x); 
    }
    return ans; 
}
void speedrun(int subtask, int Ni, int start) { 
    n = Ni; 

    if(subtask == 2){
        int root = start; 
        if(!getHint(1)){
            f(i,1,n+1){
                if(i != start and goTo(i)){
                    root = i; 
                    break; 
                }
            }
        }
        f(i,1,n+1){
            if(i != root){
                goTo(i); 
                goTo(root);
            }
        }
        return; 
    }
    if(subtask == 3){
        while(1){
            int r = get(2); 
            if(r == 0) break; 
            start = r; 
            goTo(start); 
        }
        while(1){
            int l = get(1); 
            if(l == 0) break; 
            start = l; 
            goTo(start); 
        }
        return; 
    }
    while(start != 1) {
        start = get(1); 
        goTo(start); 
    }
     
    if(get(2) != 0) curr.push_back(get(2));
    if(get(3) != 0) curr.push_back(get(3));   
    int id = 1; 
    vis[1] = 1;  

    while(id < (int) curr.size()){
        int node = curr[id]; 
        if(!goTo(node))
            return; 
        
        if(!vis[node]){
            vis[node] = 1; 
            if(get(2) != 0) curr.push_back(get(2));
            if(get(3) != 0) curr.push_back(get(3));   
        }
        id++; 
    }
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:49:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |             if(adj[i].size() == n-1){
      |                ~~~~~~~~~~~~~~^~~~~~
speedrun.cpp:65:12: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
   65 |         dfs(l, 0);
      |         ~~~^~~~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 760 KB Output is correct
2 Correct 136 ms 768 KB Output is correct
3 Correct 89 ms 740 KB Output is correct
4 Correct 116 ms 776 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 756 KB Output is correct
2 Correct 14 ms 764 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 840 KB Output is correct
2 Correct 84 ms 968 KB Output is correct
3 Correct 72 ms 860 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 808 KB Output is correct
2 Correct 123 ms 684 KB Output is correct
3 Correct 132 ms 920 KB Output is correct
4 Correct 128 ms 764 KB Output is correct
5 Correct 141 ms 744 KB Output is correct
6 Correct 104 ms 748 KB Output is correct

Subtask #5
30.0 / 40.0

# Verdict Execution time Memory Grader output
1 Partially correct 81 ms 812 KB Partial solution
2 Partially correct 137 ms 800 KB Partial solution
3 Partially correct 144 ms 884 KB Partial solution
4 Partially correct 109 ms 684 KB Partial solution
5 Partially correct 86 ms 792 KB Partial solution
6 Partially correct 110 ms 784 KB Partial solution
7 Partially correct 86 ms 692 KB Partial solution