oj.uz

Submission #93291

# Submission time Handle Problem Language Result Execution time Memory
93291 2019-01-07T12:48:15 Z Alexa2001 Amusement Park (JOI17_amusement_park) C++17
10 / 100
 31 ms 5688 KB 
#include "Joi.h"
#include <bits/stdc++.h>

typedef long long ll;
const int Nmax = 30005;
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 = 30005;
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(node != 0 && 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(it && t[it] == i) good.push_back(it);

        good.erase(unique(good.begin(), good.end()), good.end());
        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]);


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


  //  return baga(node);

    if(node == P) return baga(P);
    assert(sbrb != -1);

    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]);

    if(w[sbrb] <= 60 && w[sbrb] + T >= 60) return baga(sbrb);

    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:123:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
Ioi.cpp:130:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<S.size(); ++i)
              ~^~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2200 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5144 KB Output is correct
2 Correct 28 ms 5324 KB Output is correct
3 Correct 30 ms 5416 KB Output is correct
4 Correct 19 ms 4024 KB Output is correct
5 Correct 19 ms 4484 KB Output is correct
6 Correct 19 ms 4344 KB Output is correct
7 Correct 19 ms 4144 KB Output is correct
8 Correct 20 ms 4500 KB Output is correct
9 Correct 19 ms 4400 KB Output is correct
10 Correct 17 ms 4284 KB Output is correct
11 Correct 17 ms 4400 KB Output is correct
12 Correct 17 ms 3868 KB Output is correct
13 Incorrect 17 ms 3968 KB Wrong Answer [7]
14 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 2428 KB Output is correct
3 Correct 4 ms 2160 KB Output is correct
4 Correct 6 ms 2708 KB Output is correct
5 Correct 6 ms 2580 KB Output is correct
6 Correct 6 ms 2580 KB Output is correct
7 Correct 6 ms 2652 KB Output is correct
8 Correct 6 ms 2572 KB Output is correct
9 Correct 15 ms 4792 KB Output is correct
10 Correct 15 ms 4840 KB Output is correct
11 Correct 15 ms 4912 KB Output is correct
12 Correct 4 ms 2296 KB Output is correct
13 Correct 4 ms 2176 KB Output is correct
14 Correct 4 ms 2176 KB Output is correct
15 Correct 4 ms 2196 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5324 KB Output is correct
2 Correct 28 ms 5316 KB Output is correct
3 Correct 30 ms 5316 KB Output is correct
4 Correct 18 ms 4152 KB Output is correct
5 Correct 19 ms 4528 KB Output is correct
6 Correct 19 ms 4400 KB Output is correct
7 Correct 20 ms 4400 KB Output is correct
8 Correct 19 ms 4020 KB Output is correct
9 Correct 19 ms 4180 KB Output is correct
10 Correct 18 ms 4144 KB Output is correct
11 Correct 17 ms 4364 KB Output is correct
12 Correct 17 ms 3724 KB Output is correct
13 Correct 16 ms 3744 KB Output is correct
14 Incorrect 17 ms 3916 KB Wrong Answer [7]
15 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5412 KB Output is correct
2 Correct 27 ms 5216 KB Output is correct
3 Correct 27 ms 5688 KB Output is correct
4 Correct 19 ms 3888 KB Output is correct
5 Correct 19 ms 4788 KB Output is correct
6 Correct 18 ms 4176 KB Output is correct
7 Correct 19 ms 4156 KB Output is correct
8 Correct 31 ms 4504 KB Output is correct
9 Correct 19 ms 4156 KB Output is correct
10 Correct 18 ms 4144 KB Output is correct
11 Correct 17 ms 4144 KB Output is correct
12 Correct 17 ms 3976 KB Output is correct
13 Incorrect 17 ms 3748 KB Wrong Answer [7]
14 Halted 0 ms 0 KB -