oj.uz

Submission #859081

# Submission time Handle Problem Language Result Execution time Memory
859081 2023-10-09T16:28:33 Z lucri Speedrun (RMI21_speedrun) C++17
100 / 100
 114 ms 2104 KB 
/* Input format:
 *
 * N -- number of nodes
 * a1 b1 -- edge 1
 * ...
 * a(N-1) b(N-1) -- edge N - 1
 * x -- start node
 */

#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;

/*static map<int, map<int, bool>> mp;
static int length = -1;
static int queries = 0;
static bool length_set = false;
static int current_node = 0;
static set<int> viz;
static map<int, set<int>> neighbours;

void setHintLen(int l) {
    if (length_set) {
        cerr << "Cannot call setHintLen twice" << endl;
        exit(0);
    }
    length = l;
    length_set = true;
}

void setHint(int i, int j, bool b) {
    if (!length_set) {
        cerr << "Must call setHintLen before setHint" << endl;
        exit(0);
    }
    mp[i][j] = b;
}

int getLength() { return length; }

bool getHint(int j) { return mp[current_node][j]; }

bool goTo(int x) {
    if (neighbours[current_node].find(x) == end(neighbours[current_node])) {
        ++queries;
        return false;
    } else {
        viz.insert(current_node = x);
        return true;
    }
}*/

void codifica(int poz,int a,int b)
{
    for(int i=10;i>=1;--i)
    {
        setHint(poz,i,a%2);
        a/=2;
    }
    for(int i=20;i>=11;--i)
    {
        setHint(poz,i,b%2);
        b/=2;
    }
}
void construieste(int nod,int uc,vector<int>a[],int t[])
{
    if(nod==1)
    {
        codifica(nod,0,a[nod][0]);
        int ant=0,ac=0;
        for(auto x:a[nod])
        {
            if(ac==0)
                ac=x;
            else
            {
                ant=ac;
                ac=x;
                construieste(ant,ac,a,t);
            }
            t[x]=nod;
        }
        construieste(ac,0,a,t);
        return;
    }
    if(a[nod].size()==1)
        codifica(nod,t[nod],uc);
    else
    {
        int ant=0,ac=0;
        if(a[nod][0]!=t[nod])
            codifica(nod,t[nod],a[nod][0]);
        else
            codifica(nod,t[nod],a[nod][1]);
        for(auto x:a[nod])
        {
            if(t[nod]==x)
                continue;
            t[x]=nod;
            if(ac==0)
                ac=x;
            else
            {
                ant=ac;
                ac=x;
                construieste(ant,ac,a,t);
            }
        }
        construieste(ac,uc,a,t);
    }
}
void assignHints(int subtask, int N, int A[], int B[])
{
    setHintLen(20);
    int n=N,t[1010];
    vector<int>a[n+5];
    t[n]=0;
    for(int i=1;i<n;++i)
    {
        t[i]=0;
        a[A[i]].push_back(B[i]);
        a[B[i]].push_back(A[i]);
    }
    construieste(1,0,a,t);
}

int decodifica1()
{
    int val=0;
    for(int i=1;i<=10;++i)
    {
        val*=2;
        val+=getHint(i);
    }
    return val;
}
int decodifica2()
{
    int val=0;
    for(int i=11;i<=20;++i)
    {
        val*=2;
        val+=getHint(i);
    }
    return val;
}
void rezolva()
{
    int nod=1,du=0;
    stack<int>s;
    s.push(1);
    while(1)
    {
        while(decodifica2()!=0&&goTo(nod=decodifica2()))
            s.push(nod);
        du=decodifica2();
        if(du==0)
            break;
        s.pop();
        goTo(s.top());
        while(goTo(du)==false)
        {
            s.pop();
            goTo(s.top());
        }
        nod=du;
        s.push(nod);
        du=0;
    }
}
void speedrun(int subtask, int N, int start)
{
    while(start!=1)
        goTo(start=decodifica1());
    rezolva();
}

/*int main() {
    int N;
    cin >> N;

    int a[N], b[N];
    for (int i = 1; i < N; ++i) {
        cin >> a[i] >> b[i];
        neighbours[a[i]].insert(b[i]);
        neighbours[b[i]].insert(a[i]);
    }

    assignHints(1, N, a, b);

    if (!length_set) {
        cerr << "Must call setHintLen at least once" << endl;
        exit(0);
    }

    cin >> current_node;
    viz.insert(current_node);

    speedrun(1, N, current_node);

    if (viz.size() < N) {
        cerr << "Haven't seen all nodes" << endl;
        exit(0);
    }

    cerr << "OK; " << queries << " incorrect goto's" << endl;
    return 0;
}*/

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 1352 KB Output is correct
2 Correct 99 ms 1096 KB Output is correct
3 Correct 89 ms 1976 KB Output is correct
4 Correct 90 ms 1076 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 1312 KB Output is correct
2 Correct 91 ms 1336 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1420 KB Output is correct
2 Correct 88 ms 1084 KB Output is correct
3 Correct 104 ms 1340 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 1340 KB Output is correct
2 Correct 102 ms 1344 KB Output is correct
3 Correct 94 ms 1352 KB Output is correct
4 Correct 106 ms 1220 KB Output is correct
5 Correct 97 ms 1596 KB Output is correct
6 Correct 99 ms 1228 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 1604 KB Output is correct
2 Correct 89 ms 2104 KB Output is correct
3 Correct 112 ms 1728 KB Output is correct
4 Correct 82 ms 1336 KB Output is correct
5 Correct 93 ms 1076 KB Output is correct
6 Correct 114 ms 1344 KB Output is correct
7 Correct 90 ms 976 KB Output is correct