oj.uz

Submission #93656

# Submission time Handle Problem Language Result Execution time Memory
93656 2019-01-10T15:21:53 Z Alexa2001 Amusement Park (JOI17_amusement_park) C++17
10 / 100
 33 ms 7616 KB 
#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));
}

#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);
    }

    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

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:106:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1; i<v[node].size() && take[node]; ++i)
              ~^~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 2040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 7248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2160 KB Output is correct
2 Correct 4 ms 2160 KB Output is correct
3 Correct 4 ms 2296 KB Output is correct
4 Correct 6 ms 2708 KB Output is correct
5 Correct 6 ms 2632 KB Output is correct
6 Correct 6 ms 2572 KB Output is correct
7 Correct 7 ms 2732 KB Output is correct
8 Correct 6 ms 2736 KB Output is correct
9 Correct 16 ms 4784 KB Output is correct
10 Correct 15 ms 4920 KB Output is correct
11 Correct 15 ms 4788 KB Output is correct
12 Correct 4 ms 2160 KB Output is correct
13 Correct 4 ms 2416 KB Output is correct
14 Correct 4 ms 2172 KB Output is correct
15 Correct 4 ms 2160 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 7616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 31 ms 7236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -