oj.uz

Submission #93269

# Submission time Handle Problem Language Result Execution time Memory
93269 2019-01-07T11:38:54 Z Alexa2001 Amusement Park (JOI17_amusement_park) C++17
8 / 100
 30 ms 6400 KB 
#include "Joi.h"
#include <bits/stdc++.h>

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

static bool used[Nmax];
static vector<int> v[Nmax];
static int bit, w[Nmax], t[Nmax];
static ll TO;

static void dfs_sel_edges(int node)
{
    used[node] = 1;
    w[node] = 1;

    for(auto it : v[node])
        if(!used[it])
        {
            t[it] = node;
            dfs_sel_edges(it);
            w[node] += w[it];
        }
}

static void dfs(int node)
{
    MessageBoard(node, (TO >> bit) & 1);
    for(auto it : v[node])
        {
            bit = (bit+1) % 60;
            dfs(it);
        }
}

static bool cmp(int a, int b)
{
    return w[a] < w[b];
}

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

    t[0] = -1;
    dfs_sel_edges(0);

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

    for(i=0; i<N; ++i)
        sort(v[i].begin(), v[i].end(), cmp);

    bit = 0;
    dfs(0);
}

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

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

static bool used[Nmax], to_visit[Nmax];
static vector<int> v[Nmax];
static int bit, w[Nmax], t[Nmax], In[Nmax], ord[Nmax], tip[Nmax], tmp, Special;

ll Act, Mask;

static void dfs_sel_edges(int node)
{
    used[node] = 1;
    w[node] = 1;

    for(auto it : v[node])
        if(!used[it])
        {
            t[it] = node;
            dfs_sel_edges(it);
            w[node] += w[it];
        }
}

static void dfs(int node)
{
    tip[node] = bit;
    In[node] = ++tmp;
    ord[tmp] = node;

    for(auto it : v[node])
        {
            bit = (bit+1) % 60;
            dfs(it);
            ord[++tmp] = node;
        }
}

bool cmp(int a, int b)
{
    return w[a] < w[b];
}

static void go(int node)
{
    to_visit[node] = 0;
    for(auto it : v[node])
        if(to_visit[it])
        {
            Act |= (1LL<<tip[it]) * Move(it);
            go(it);
            Move(node);
        }

    if(to_visit[t[node]])
    {
        Act |= (1LL<<tip[t[node]]) * Move(t[node]);
        go(t[node]);
    }
}

static ll baga(int node)
{
    int i;
    for(i=In[node]; (!to_visit[Special] || Mask != AllBits) && i <= tmp; ++i)
        to_visit[ord[i]] = 1, Mask |= (1LL << tip[ord[i]]);

    assert(to_visit[Special] && Mask == AllBits);

    go(Special);
    return Act;
}

ll Ioi(int N, int M, int A[], int B[], int P, int V, int _T)
{
    Special = P;

    int i;
    for(i=0; i<M; ++i)
    {
        v[A[i]].push_back(B[i]);
        v[B[i]].push_back(A[i]);
    }

    dfs_sel_edges(0);

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

    for(i=0; i<N; ++i)
        sort(v[i].begin(), v[i].end(), cmp);

    bit = 0;
    dfs(0);

    Mask = (1LL << tip[P]);
    Act = V * (1LL << tip[P]);

    return baga(0);

    int node = P, sbrb;
    while(w[node] < 60) sbrb = node, node = t[node];


    if(node == P)
        return baga(P);

    vector<int> S;
    bool ok = 0; int T = 0;

    for(i=0; i<v[node].size(); ++i)
        if(v[node][i] == sbrb) ok = 1;
            else if(!ok) S.push_back(w[v[node][i]]);
                else T += w[v[node][i]];

    for(i=(int)S.size()-2; i>=0; --i) S[i] += S[i+1];

    for(i=0; i<S.size(); ++i)
        if(S[i] + w[sbrb] <= 60 && S[i] + w[sbrb] + T >= 60)
            return baga(v[node][i]);

    assert(T == 0);

    for(i=S.size()-1; i>=0; --i)
        if(S[i] + w[sbrb] >= 60) baga(v[node][i]);

    return baga(node);
}

Compilation message

Ioi.cpp: In function 'll Ioi(int, int, int*, int*, int, int, int)':
Ioi.cpp:121:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
Ioi.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<S.size(); ++i)
              ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1268 KB Output is correct
2 Correct 4 ms 1668 KB Output is correct
3 Correct 4 ms 1404 KB Output is correct
4 Correct 4 ms 1276 KB Output is correct
5 Correct 4 ms 1396 KB Output is correct
6 Correct 4 ms 1520 KB Output is correct
7 Correct 4 ms 1400 KB Output is correct
8 Correct 4 ms 1520 KB Output is correct
9 Correct 4 ms 1500 KB Output is correct
10 Correct 4 ms 1268 KB Output is correct
11 Correct 7 ms 1620 KB Output is correct
12 Correct 4 ms 1276 KB Output is correct
13 Correct 4 ms 1280 KB Output is correct
14 Correct 4 ms 1476 KB Output is correct
15 Correct 4 ms 1436 KB Output is correct
16 Correct 4 ms 1280 KB Output is correct
17 Correct 4 ms 1272 KB Output is correct
18 Correct 5 ms 1272 KB Output is correct

Subtask #2
0 / 10.0

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

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1264 KB Output is correct
2 Correct 4 ms 1264 KB Output is correct
3 Correct 4 ms 1300 KB Output is correct
4 Correct 6 ms 1680 KB Output is correct
5 Incorrect 6 ms 1740 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4476 KB Output is correct
2 Runtime error 30 ms 6276 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

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