Submission #645864

#	Time	Username	Problem	Language	Result	Execution time	Memory
645864		MadokaMagicaFan	Speedrun (RMI21_speedrun)	C++14	48 / 100	185 ms	812 KiB

speedrun

#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;

#define forn(i,n)   for(int i = 0; i < n; ++i)
#define forb(i,b,n)   for(int i = b; i < n; ++i)
#define pb          push_back
#define sz(v)       ((int)((v).size()))

/* #define ONPC */

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

vi p;

void setb(int a, int b) {
    forn(j,10) {
        if (b&(1<<j))
            setHint(a,j+11,1);
        else
            setHint(a,j+11,0);
    }
}

void setx(int a, int b) {
    /* cout << a << ' ' << b << endl; */
    forn(j,10) {
        if (b&(1<<j))
            setHint(a,j+1,1);
        else
            setHint(a,j+1,0);
    }
}

void bfs(int x, int p, vector<vector<int>> &adj) {
    vi eadj;
    for(int u : adj[x])
        if (u != p)
            eadj.pb(u);

    int small = (sz(eadj) > 0) ? eadj[0] : 0;
    forb(i, 1, sz(eadj)) {
        setb(eadj[i], eadj[i-1]);
        small = min(small, eadj[i]);
    }
    if (sz(eadj))
        setb(eadj[0], eadj[sz(eadj) - 1]);

    /* cout << x << ' ' << p << ' ' << (p^small) << endl; */
    setx(x, p^small);

    for(int u : adj[x])
        if (u != p)
            bfs(u,x,adj);
}

void
assignHints(int s, int n, int *a, int *b)
{
    if (s == 1) {
        setHintLen(n);
        forb(i,1,n) {
            setHint(a[i], b[i], 1);
            setHint(b[i], a[i], 1);
        }
    } else if (s == 2) {
        setHintLen(20);
        int spec = 0;
        if (n == 2)
            spec = 1;
        else {
            if (a[1] == a[2])
                spec = a[1];
            if (b[1] == b[2])
                spec = b[1];
            if (a[1] == b[2])
                spec = a[1];
            if (b[1] == a[2])
                spec = b[1];
        }

        forb(i,1, n+1) {
            forn(j, 10) {
                if (spec&(1<<j))
                    setHint(i,j+1,1);
            }
        }
    } else if (s == 3) {
        setHintLen(20);
        vi cn(n+1,0);
        /* forb(i, 1, n+1) { */
        /*     forn(j,10) { */
        /*         if (i&(1<<j)) */
        /*             setHint(i,j+1,1); */
        /*         if (i&(1<<j)) */
        /*             setHint(i,j+11,1); */
        /*     } */
        /* } */

        forb(i, 1, n) {
            /* cout << cn[a[i]] << ' ' << cn[b[i]] << endl; */
            forn(j,10) {
                if (a[i]&(1<<j))
                    setHint(b[i], j+1+10*cn[b[i]], 1);
                else
                    setHint(b[i], j+1+10*cn[b[i]], 0);
                if (b[i]&(1<<j))
                    setHint(a[i], j+1+10*cn[a[i]], 1);
                else
                    setHint(a[i], j+1+10*cn[a[i]], 0);
            }
            ++cn[a[i]];
            ++cn[b[i]];
        }
    } else {
        setHintLen(20);

        vector<vector<int>> adj(n+1);
        forb(i,1,n) {
            adj[a[i]].pb(b[i]);
            adj[b[i]].pb(a[i]);
        }

        bfs(1,1,adj);
    }


}

void dfs1(int x, int n)
{
    forb(i,1,n+1) {
        if (x == i) continue;
        if (i == p[x]) continue;

        if (getHint(i)) {
            p[i] = x;
            goTo(i);
            dfs1(i,n);
            goTo(x);
        }

    }
}

void dfs3(int x, int p) {
    int nx = 0;

    forn(j, 10)
        if (getHint(j+1))
            nx |= 1<<j;

    if (nx != p && nx != 0) {
        goTo(nx);
        dfs3(nx,x);
        goTo(x);
    }

    nx = 0;

    forn(j, 10)
        if (getHint(j+11))
            nx |= 1<<j;

    if (nx != p && nx != 0) {
        goTo(nx);
        dfs3(nx,x);
        goTo(x);
    }
}

int
getx()
{
    int x = 0;
    forn(j, 10)
        if (getHint(j+1))
            x |= 1<<j;

    return x;
}

int
getb()
{
    int x = 0;
    forn(j, 10)
        if (getHint(j+11))
            x |= 1<<j;

    return x;
}

int depth_dfs(int x ,int cp) {
    if (x == 1)
        return 1;

    int l = getx();

    if ((l^cp) == 0) {
        goTo(cp);
        return 0;
    }

    goTo(l^cp);
    if (depth_dfs(l^cp, x))
        return 1;

    goTo(cp);
    return 0;
}

int solve(int x, int p) {
    int c = getx() ^ p;
    int b = getb();

    if (c == 0) {
    /* cout << "R" << ' ' << x << ' ' << b << endl; */
     return b;
    }

    int u = c;
    char z;
    /* cin >> z; */

    do {
        /* cout << x << ' ' << u << endl; */
        goTo(u);
        u = solve(u, x);
        goTo(x);
    } while ( u != c );

    /* cout << "R" << ' ' << x << ' ' << b << endl; */
    return b;
}
int cur;

void
speedrun(int s, int n, int x) {
    if (n == 1)
        return;
    if (s == 1) {
        p.assign(n+1, -1);
        dfs1(x,n);
    } else if (s == 2) {
        int spec = 0;

        forn(j, 10) {
            if (getHint(j+1))
                spec |= 1<<j;
        }

        goTo(spec);

        forb(i, 1, n+1) {
            goTo(i);
            goTo(spec);
        }
    } else if (s == 3) {
        dfs3(x,x);
    } else {
        if (x > 1) {
            forb (i, 1, n+1) {
                if (goTo(i)) {
                    if (depth_dfs(i,x))
                        break;
                }
            }
        }

        return;
        solve(1,1);
    }
}


#ifdef ONPC
int lg;
vector<bool> vis;
int cnt = 0;
int mist = 0;;
const int N = 1000;
int a[N+1], b[N+1];
vector<vector<bool>> h;
void setHintLen(int l){
    lg = l;
    forn(i, sz(h))
        h[i].assign(l,0);
}

void setHint(int i, int j, bool b) {
    --i, --j;
    assert(i < sz(h));
    assert(j < lg);
    h[i][j] = b;
}

int getLength() {
    return lg;
}
bool getHint(int j) {
    j--;
    assert(j < lg);
    return h[cur][j];
}
bool goTo(int x) {
    for(int i = 1; i < sz(h); ++i) {
        if (a[i] == cur+1 && b[i] == x
         || b[i] == cur+1 && a[i] == x ) {
            cur = x - 1;
            if (vis[cur] == 0) {
                vis[cur] = 1;
                ++cnt;
            }
            return 1;
        }
    }
    ++mist;
    return 0;
}



int32_t
main(int argc, char *argv[])
{
    if (argc > 1)
        freopen(argv[1], "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    int sub, n, st;

    cin >> sub >> n >> st;

    cur = st-1;

    h.assign(n,{});
    vis.assign(n,0);

    vis[st-1] = 1;
    cnt = 1;

    for (int i = 1; i < n; ++i) {
        cin >> a[i] >> b[i];
    }

    assignHints(sub, n, a, b);
    speedrun(sub, n, st);

    cout << cnt << ' ' << mist;
}
#endif

Compilation message (stderr)

speedrun.cpp: In function 'int solve(int, int)':
speedrun.cpp:231:10: warning: unused variable 'z' [-Wunused-variable]
  231 |     char z;
      |          ^

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