Submission #93949

#	Time	Username	Problem	Language	Result	Execution time	Memory
93949		Alexa2001	Amusement Park (JOI17_amusement_park)	C++17	100 / 100	30 ms	5452 KiB

Joi

#include "Joi.h"
#include <bits/stdc++.h>

typedef long long ll;
const int Nmax = 30005;
using namespace std;


static int tmp;
static bool used[Nmax];
static int In[Nmax], w[Nmax], level[Nmax], down[Nmax], t[Nmax];
static vector<int> v[Nmax];


static void dfs1(int node = 0)
{
    used[node] = 1;
    down[node] = 1;
    w[node] = 1;

    for(auto it : v[node])
        if(!used[it])
        {
            t[it] = node;
            level[it] = level[node] + 1;
            dfs1(it);
            w[node] += w[it];
            down[node] = max(down[node], down[it] + 1);
        }
}

static void change_edges(int N)
{
    int i;
    for(i=0; i<N; ++i)
    {
        vector<int> good;
        for(auto it : v[i])
            if(t[it] == i)
                good.push_back(it);

        int j, act = 0;
        for(j=0; j<good.size(); ++j)
            if(down[good[j]] > down[good[act]]) act = j;

        if(!good.empty()) swap(good[act], good[0]);
        v[i] = good;
    }
}

static void dfs2(int node = 0)
{
    In[node] = ++tmp;
    for(auto it : v[node]) dfs2(it);
}

void Joi(int N, int M, int A[], int B[], ll X, int _T)
{
    int i;
    for(i=0; i<M; ++i)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }

    dfs1();
    change_edges(N);

    if(down[0] >= 60) /// coloreaza pe inaltimi si gata
    {
        for(i=0; i<N; ++i)
            MessageBoard(i, (X >> (level[i] % 60)) &1);
        return;
    }

  //  assert(0);

    dfs2();

    for(i=0; i<N; ++i)
        MessageBoard(i, (X >> (In[i] % 60)) &1);
}

Ioi

#include "Ioi.h"
#include <bits/stdc++.h>

typedef long long ll;
const int Nmax = 30005;
const ll AllBits = (1LL << 60) - 1;
using namespace std;

static int tmp;
static bool used[Nmax];
static int ord[Nmax], In[Nmax], w[Nmax], level[Nmax], down[Nmax], t[Nmax], take[Nmax];
static vector<int> v[Nmax];
static bool Down = 0;

static void dfs1(int node = 0)
{
    used[node] = 1;
    down[node] = 1;
    w[node] = 1;

    for(auto it : v[node])
        if(!used[it])
        {
            t[it] = node;
            level[it] = level[node] + 1;
            dfs1(it);
            w[node] += w[it];
            down[node] = max(down[node], down[it] + 1);
        }
}

static void change_edges(int N)
{
    int i;
    for(i=0; i<N; ++i)
    {
        vector<int> good;
        for(auto it : v[i])
            if(t[it] == i)
                good.push_back(it);

        int j, act = 0;
        for(j=0; j<good.size(); ++j)
            if(down[good[j]] > down[good[act]]) act = j;

        if(!good.empty()) swap(good[act], good[0]);
        v[i] = good;
    }
}

static void dfs2(int node = 0)
{
    In[node] = ++tmp; ord[tmp] = node;
    for(auto it : v[node]) dfs2(it);
}

static ll solve1(int node, ll Mask, ll Ans)
{
    if(Mask == AllBits) return Ans;
    if(node == 0) Down = 1;
    if(Down)
    {
        ///!!
        assert(v[node].size());
        ll w = (1LL << (level[v[node][0]] % 60));
        ll res = Move(v[node][0]) * w;
        return solve1(v[node][0], Mask | w,  Ans | res);
    }
    else
    {
        ll w = (1LL << (level[t[node]] % 60));
        ll res = Move(t[node]) * w;
        return solve1(t[node], Mask | w,  Ans | res);
    }
}

static void solve2(int node, ll &Mask, ll &Ans, int &cnt)
{
    if(Mask == AllBits)
    {
        ///!!
       // assert(node == ord[down[0]]);
        return;
    }

    if(cnt < 0) assert(In[node] <= down[0]);
        else assert(In[node] > down[0]);

    if(In[node] > down[0])
    {
        ///!!
        assert(cnt >= 1);
        --cnt;

        for(auto it : v[node])
            if(cnt > 0)
            {
                int res = Move(it);
                Mask |= (1LL << (In[it] % 60));
                if(res) Ans |= (1LL << (In[it] % 60));
                solve2(it, Mask, Ans, cnt);
                Move(node);
            }
       // assert(cnt == 0);
        return;
    }

    int i;
    for(i=1; i<v[node].size() && take[node]; ++i)
    {
        int x = v[node][i], pos = min(w[x], take[node]);
        int res = Move(x);

        Mask |= (1LL << (In[x] % 60));
        if(res) Ans |= (1LL << (In[x] % 60));

        take[node] -= pos;
        solve2(x, Mask, Ans, pos);
        Move(node);

        assert(pos == 0);
    }
    assert(take[node] == 0);

    int x = v[node][0];
    int res = Move(x);

    Mask |= (1LL << (In[x] % 60));
    if(res) Ans |= (1LL << (In[x] % 60));

    solve2(x, Mask, Ans, cnt);
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int _T)
{
    int i;
    for(i=0; i<M; ++i)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }

    dfs1();
    change_edges(N);

    if(down[0] >= 60) /// coloreaza pe inaltimi si gata
        return solve1(P, (1LL << (level[P] % 60)), V * (1LL << (level[P] % 60)));

    dfs2();

    int rest = 60 - down[0];
    for(i=down[0] - 1; i; --i)
    {
        int node, sub;
        node = ord[i];
        sub = w[node] - w[ord[i+1]] - 1;
        take[node] = min(sub, rest);
        rest -= take[node];
    }

    assert(rest == 0);

    ll Mask, Ans;
    Mask = (1LL << (In[P] % 60));
    Ans = V * Mask;

    while(P)
    {
        P = t[P];
        int res = Move(P);
        Mask |= (1LL << (In[P] % 60));
        if(res) Ans |= (1LL << (In[P] % 60));
    }
    int cnt = -1;
    solve2(0, Mask, Ans, cnt);
    return Ans;
}

Compilation message (stderr)

Joi.cpp: In function 'void change_edges(int)':
Joi.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<good.size(); ++j)
                  ~^~~~~~~~~~~~

Ioi.cpp: In function 'void change_edges(int)':
Ioi.cpp:43:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<good.size(); ++j)
                  ~^~~~~~~~~~~~
Ioi.cpp: In function 'void solve2(int, ll&, ll&, int&)':
Ioi.cpp:109:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<v[node].size() && take[node]; ++i)
              ~^~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 55 / 55
• Subtask 5: 17 / 17