oj.uz

답안 #93948

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93948 2019-01-13T16:41:10 Z Alexa2001 Amusement Park (JOI17_amusement_park) C++17
18 / 100
 28 ms 6080 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);
    }
    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

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
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2160 KB Output is correct
2 Correct 4 ms 2160 KB Output is correct
3 Correct 6 ms 2164 KB Output is correct
4 Correct 4 ms 2160 KB Output is correct
5 Correct 5 ms 2160 KB Output is correct
6 Correct 5 ms 2160 KB Output is correct
7 Correct 4 ms 2304 KB Output is correct
8 Correct 4 ms 2176 KB Output is correct
9 Correct 4 ms 2164 KB Output is correct
10 Correct 4 ms 2296 KB Output is correct
11 Correct 8 ms 2544 KB Output is correct
12 Correct 4 ms 2160 KB Output is correct
13 Correct 5 ms 2412 KB Output is correct
14 Correct 6 ms 2164 KB Output is correct
15 Correct 5 ms 2168 KB Output is correct
16 Correct 5 ms 2300 KB Output is correct
17 Correct 4 ms 2300 KB Output is correct
18 Correct 5 ms 2164 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 5636 KB Output is correct
2 Correct 27 ms 5732 KB Output is correct
3 Correct 28 ms 5596 KB Output is correct
4 Correct 19 ms 4204 KB Output is correct
5 Correct 19 ms 4344 KB Output is correct
6 Correct 20 ms 4600 KB Output is correct
7 Correct 19 ms 4472 KB Output is correct
8 Correct 19 ms 4476 KB Output is correct
9 Correct 19 ms 4472 KB Output is correct
10 Correct 17 ms 4476 KB Output is correct
11 Correct 18 ms 4484 KB Output is correct
12 Correct 18 ms 3936 KB Output is correct
13 Correct 17 ms 4064 KB Output is correct
14 Correct 18 ms 4220 KB Output is correct
15 Correct 20 ms 4220 KB Output is correct
16 Correct 19 ms 4220 KB Output is correct
17 Correct 19 ms 4216 KB Output is correct
18 Correct 19 ms 4232 KB Output is correct
19 Runtime error 20 ms 6048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2208 KB Output is correct
2 Correct 4 ms 2160 KB Output is correct
3 Correct 4 ms 2160 KB Output is correct
4 Correct 6 ms 2788 KB Output is correct
5 Correct 6 ms 2700 KB Output is correct
6 Correct 6 ms 2708 KB Output is correct
7 Correct 6 ms 2704 KB Output is correct
8 Correct 6 ms 2572 KB Output is correct
9 Correct 16 ms 5028 KB Output is correct
10 Correct 15 ms 4984 KB Output is correct
11 Correct 15 ms 4856 KB Output is correct
12 Correct 5 ms 2172 KB Output is correct
13 Correct 4 ms 2296 KB Output is correct
14 Correct 4 ms 2184 KB Output is correct
15 Correct 4 ms 2176 KB Output is correct

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 5728 KB Output is correct
2 Correct 27 ms 5748 KB Output is correct
3 Correct 27 ms 5748 KB Output is correct
4 Correct 20 ms 4224 KB Output is correct
5 Correct 19 ms 4776 KB Output is correct
6 Correct 19 ms 4356 KB Output is correct
7 Correct 19 ms 4356 KB Output is correct
8 Correct 17 ms 4248 KB Output is correct
9 Correct 19 ms 4468 KB Output is correct
10 Correct 15 ms 4484 KB Output is correct
11 Correct 17 ms 4512 KB Output is correct
12 Correct 17 ms 4072 KB Output is correct
13 Correct 17 ms 3956 KB Output is correct
14 Correct 17 ms 4220 KB Output is correct
15 Correct 19 ms 4244 KB Output is correct
16 Correct 19 ms 4232 KB Output is correct
17 Correct 19 ms 4360 KB Output is correct
18 Runtime error 20 ms 6080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 5588 KB Output is correct
2 Correct 27 ms 5756 KB Output is correct
3 Correct 27 ms 5684 KB Output is correct
4 Runtime error 20 ms 6048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -