oj.uz

Submission #93289

# Submission time Handle Problem Language Result Execution time Memory
93289 2019-01-07T12:29:21 Z Alexa2001 Amusement Park (JOI17_amusement_park) C++17
10 / 100
 38 ms 5444 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(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]);


    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:122:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
Ioi.cpp:129: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 5 ms 2304 KB Wrong Answer [7]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 5328 KB Output is correct
2 Correct 30 ms 5432 KB Output is correct
3 Correct 38 ms 5408 KB Output is correct
4 Correct 17 ms 3920 KB Output is correct
5 Correct 18 ms 4400 KB Output is correct
6 Correct 18 ms 4144 KB Output is correct
7 Correct 19 ms 4144 KB Output is correct
8 Correct 19 ms 4476 KB Output is correct
9 Correct 19 ms 4488 KB Output is correct
10 Correct 16 ms 4144 KB Output is correct
11 Correct 17 ms 4372 KB Output is correct
12 Correct 17 ms 3704 KB Output is correct
13 Incorrect 16 ms 3872 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 2172 KB Output is correct
3 Correct 4 ms 2172 KB Output is correct
4 Correct 6 ms 2700 KB Output is correct
5 Correct 6 ms 2700 KB Output is correct
6 Correct 6 ms 2792 KB Output is correct
7 Correct 7 ms 2648 KB Output is correct
8 Correct 7 ms 2780 KB Output is correct
9 Correct 15 ms 4892 KB Output is correct
10 Correct 15 ms 4912 KB Output is correct
11 Correct 15 ms 4792 KB Output is correct
12 Correct 5 ms 2160 KB Output is correct
13 Correct 4 ms 2160 KB Output is correct
14 Correct 5 ms 2168 KB Output is correct
15 Correct 4 ms 2216 KB Output is correct

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5316 KB Output is correct
2 Correct 28 ms 5420 KB Output is correct
3 Correct 30 ms 5324 KB Output is correct
4 Correct 18 ms 3888 KB Output is correct
5 Correct 19 ms 4480 KB Output is correct
6 Correct 19 ms 4400 KB Output is correct
7 Correct 19 ms 4352 KB Output is correct
8 Correct 19 ms 4024 KB Output is correct
9 Correct 20 ms 4144 KB Output is correct
10 Correct 17 ms 4408 KB Output is correct
11 Correct 18 ms 4144 KB Output is correct
12 Correct 16 ms 3748 KB Output is correct
13 Correct 17 ms 3872 KB Output is correct
14 Incorrect 17 ms 4116 KB Wrong Answer [7]
15 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5444 KB Output is correct
2 Correct 28 ms 5316 KB Output is correct
3 Correct 28 ms 5420 KB Output is correct
4 Correct 17 ms 3888 KB Output is correct
5 Correct 20 ms 4656 KB Output is correct
6 Correct 20 ms 4280 KB Output is correct
7 Correct 18 ms 4156 KB Output is correct
8 Correct 19 ms 4280 KB Output is correct
9 Correct 19 ms 4280 KB Output is correct
10 Correct 17 ms 4144 KB Output is correct
11 Correct 18 ms 4168 KB Output is correct
12 Correct 17 ms 4104 KB Output is correct
13 Incorrect 17 ms 4220 KB Wrong Answer [7]
14 Halted 0 ms 0 KB -