제출 #642512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
642512		Tenis0206	Speedrun (RMI21_speedrun)	C++17	0 / 100	390 ms	748 KiB

speedrun

#include <bits/stdc++.h>

//#define home

#ifndef home

#include "speedrun.h"

#endif // home

using namespace std;

#ifdef home

int nn;
int aa[100005],bb[100005];

int mask[100005];

int cnod;

bool sel[100005];

void setHintLen(int l)
{
    return;
}

void setHint(int i, int j, bool b)
{
    if(b)
    {
        mask[i] += (1<<j);
    }
}

int getLength()
{
    return 0;
}

bool getHint(int b)
{
    return ((mask[cnod] & (1<<b)) != 0);
}

bool goTo(int x)
{
    for(int i=1;i<nn;i++)
    {
        if(aa[i]==x && bb[i]==cnod)
        {
            cnod = x;
            sel[cnod] = true;
            return true;
        }
        if(aa[i]==cnod && bb[i]==x)
        {
            cnod = x;
            sel[cnod] = true;
            return true;
        }
    }
    return false;
}

#endif // home

int l[1005],t[1005];

vector<int> G[1005];

int poz = 0;

void dfs(int nod, int dad = 0)
{
    l[++poz] = nod;
    for(auto it : G[nod])
    {
        if(it==dad)
        {
            continue;
        }
        t[it] = nod;
        dfs(it,nod);
    }
}

void setDad(int nod, int dad)
{
    for(int b=0;b<10;b++)
    {
        bool val = ((dad & (1<<b)) != 0);
        setHint(nod,b+1,val);
    }
}

void setNext(int nod, int next)
{
    for(int b=0;b<10;b++)
    {
        bool val = ((next & (1<<b)) != 0);
        setHint(nod,b+11,val);
    }
}

void assignHints(int subtask, int n, int a[], int b[])
{
    setHintLen(20);
    for(int i=1;i<n;i++)
    {
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        setDad(l[i],t[i]);
        setNext(l[i],l[i+1]);
    }
}

int getDad(int nod)
{
    int rez = 0;
    for(int b=0;b<10;b++)
    {
        int val = getHint(b + 1);
        rez += val * (1<<b);
    }
    return rez;
}

int getNext(int nod)
{
    int rez = 0;
    for(int b=0;b<10;b++)
    {
        int val = getHint(b + 11);
        rez += val * (1<<b);
    }
    return rez;
}

void speedrun(int subtask, int n, int start)
{
    getLength();
    int nod = start;
    while(nod!=1)
    {
        int dad = getDad(nod);
        goTo(dad);
        nod = dad;
    }
    for(int i=1;i<n;i++)
    {
        int next = getNext(nod);
        bool ok = goTo(next);
        while(!ok)
        {
            int dad = getDad(nod);
            goTo(dad);
            nod = dad;
            ok = goTo(next);
        }
    }
}

#ifdef home

int main()
{
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    cin>>nn;
    for(int i=1;i<nn;i++)
    {
        cin>>aa[i]>>bb[i];
    }
    assignHints(0,nn,aa,bb);
    cin>>cnod;
    sel[cnod] = true;
    speedrun(0,nn,cnod);
    bool ok = true;
    for(int i=1;i<=nn;i++)
    {
        ok &= sel[i];
    }
    if(ok)
    {
        cout<<"BRAVO BOSS";
    }
    else
    {
        cout<<"MECI MAI COX";
    }
    return 0;
}

#endif // home

• Subtask 1: 0 / 21
• Subtask 2: 0 / 8
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40