oj.uz

Submission #107131

# Submission time Handle Problem Language Result Execution time Memory
107131 2019-04-22T06:49:37 Z szawinis Amusement Park (JOI17_amusement_park) C++17
18 / 100
 41 ms 4904 KB 
#include "Joi.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+1;

void dfs(int u, vector<vector<int> > &g, vector<int> &pre, int &tick, long long X) {
    pre[u] = ++tick;
    for(int v: g[u]) {
        if(pre[v]) continue;
        dfs(v, g, pre, tick, X);
    }
    MessageBoard(u, X >> ((pre[u] - 1) % 60) & 1);
}

void Joi(int n, int m, int A[], int B[], long long X, int T) {
    vector<vector<int> > g(n + 1);
    vector<int> pre(n + 1);
    int tick = 0;
    for(int i = 0; i < m; i++) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    dfs(0, g, pre, tick, X);
}

#include "Ioi.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4+1;

void dfs(int u, vector<vector<int> > &g, vector<int> &d, vector<int> &par, vector<int> &pre, vector<int>& rev, int &tick) {
    pre[u] = ++tick;
    for(int v: g[u]) {
        if(pre[v]) continue;
        d[v] = d[u] + 1;
        par[v] = u;
        dfs(v, g, d, par, pre, rev, tick);
    }
//    cerr << u << ' ' << pre[u] << endl;
}

int get_lca(int u, int v, vector<int> &d, vector<int> &par) {
    if(d[u] < d[v]) swap(u, v);
    while(d[u] > d[v]) u = par[u];
    while(u != v) {
        u = par[u];
        v = par[v];
    }
    return u;
}

long long moveToNext(int u, int v, vector<int> &d, vector<int> &par) {
    int org_u = u, org_v = v;
    int lca = get_lca(u, v, d, par);
//    cerr << "Ioi_moveToNext " << u <<' ' << v << ' ' << lca << endl;
    vector<int> ord1, ord2;
    while(u != lca) {
        ord1.push_back(u);
        u = par[u];
    }
    while(v != lca) {
        ord2.push_back(v);
        v = par[v];
    }


    vector<int> ord = ord1;
    ord.push_back(lca);
    for(int i = ord2.size() - 1; i >= 0; i--) ord.push_back(ord2[i]);
    ord.erase(ord.begin());

    assert(ord.back() == org_v);

//    for(int x: ord) cerr << x << ' ';
//    cerr << endl;

    int ret = -1;
    for(int x: ord) ret = Move(x);
    return ret;
}

long long Ioi(int n, int m, int A[], int B[], int P, int V, int T) {

    vector<vector<int> > g(n + 1);
    vector<int> d(n + 1), par(n + 1), pre(n + 1), rev(n + 1);
    int tick = 0;

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

    dfs(0, g, d, par, pre, rev, tick);
    for(int i = 0; i < n; i++) {
        --pre[i];
        rev[pre[i]] = i;
//        cerr << "Ioi_pre " << i << ' ' << pre[i] << endl;
    }
//    for(int i = 0; i < n; i++) {
//        cerr << "Ioi_rev " << i << ' ' << rev[i] << endl;
//    }


    long long ret = 1ll * V << pre[P] % 60;
    int curr = P;
    for(int step = 1; step < 60; step++) {
        int pos = (pre[P] + step) % 60;
        int nxt = rev[pre[P] + step < n ? pre[P] + step : (pre[P] + step) % 60];
        assert(0 <= curr && curr < n && 0 <= nxt && nxt < n && curr != nxt);
        assert(pos == pre[nxt] % 60);
//        cerr << "Ioi_iterate " << nxt << ' ' << pre[nxt] % 60 << endl;
        ret += moveToNext(curr, nxt, d, par) << pos;
        curr = nxt;
    }
//    cerr << ret << endl;
    return ret;
}

Compilation message

Ioi.cpp: In function 'long long int moveToNext(int, int, std::vector<int>&, std::vector<int>&)':
Ioi.cpp:28:9: warning: unused variable 'org_u' [-Wunused-variable]
     int org_u = u, org_v = v;
         ^~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 548 KB Output is correct
2 Correct 5 ms 776 KB Output is correct
3 Correct 5 ms 900 KB Output is correct
4 Correct 4 ms 1020 KB Output is correct
5 Correct 4 ms 896 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 5 ms 936 KB Output is correct
8 Correct 5 ms 912 KB Output is correct
9 Correct 5 ms 780 KB Output is correct
10 Correct 6 ms 772 KB Output is correct
11 Correct 8 ms 1244 KB Output is correct
12 Correct 4 ms 856 KB Output is correct
13 Correct 6 ms 784 KB Output is correct
14 Correct 6 ms 968 KB Output is correct
15 Correct 5 ms 1044 KB Output is correct
16 Correct 5 ms 784 KB Output is correct
17 Correct 5 ms 964 KB Output is correct
18 Correct 6 ms 844 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4484 KB Output is correct
2 Correct 32 ms 4464 KB Output is correct
3 Correct 37 ms 4596 KB Output is correct
4 Correct 25 ms 3004 KB Output is correct
5 Correct 22 ms 3788 KB Output is correct
6 Correct 19 ms 3512 KB Output is correct
7 Correct 19 ms 3392 KB Output is correct
8 Correct 19 ms 3504 KB Output is correct
9 Correct 24 ms 3652 KB Output is correct
10 Correct 19 ms 3024 KB Output is correct
11 Correct 16 ms 3004 KB Output is correct
12 Correct 27 ms 2900 KB Output is correct
13 Correct 18 ms 2760 KB Output is correct
14 Correct 17 ms 2764 KB Output is correct
15 Correct 20 ms 3020 KB Output is correct
16 Correct 20 ms 2872 KB Output is correct
17 Correct 20 ms 3000 KB Output is correct
18 Correct 24 ms 2756 KB Output is correct
19 Correct 24 ms 2884 KB Output is correct
20 Correct 17 ms 3796 KB Output is correct
21 Correct 18 ms 3924 KB Output is correct
22 Correct 19 ms 3352 KB Output is correct
23 Correct 24 ms 3660 KB Output is correct
24 Correct 19 ms 3524 KB Output is correct
25 Correct 26 ms 3640 KB Output is correct
26 Correct 22 ms 3660 KB Output is correct
27 Correct 25 ms 3764 KB Output is correct
28 Correct 25 ms 3648 KB Output is correct
29 Correct 19 ms 3428 KB Output is correct
30 Correct 20 ms 3404 KB Output is correct
31 Correct 6 ms 908 KB Output is correct
32 Correct 6 ms 864 KB Output is correct
33 Correct 4 ms 1000 KB Output is correct
34 Correct 6 ms 900 KB Output is correct
35 Correct 4 ms 908 KB Output is correct
36 Correct 15 ms 1020 KB Output is correct
37 Correct 4 ms 760 KB Output is correct
38 Correct 5 ms 780 KB Output is correct
39 Correct 4 ms 772 KB Output is correct
40 Correct 5 ms 772 KB Output is correct
41 Correct 5 ms 856 KB Output is correct
42 Correct 4 ms 908 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 4 ms 992 KB Output is correct
3 Correct 4 ms 904 KB Output is correct
4 Correct 6 ms 1312 KB Output is correct
5 Correct 7 ms 1436 KB Output is correct
6 Correct 7 ms 1444 KB Output is correct
7 Correct 6 ms 1436 KB Output is correct
8 Incorrect 10 ms 1436 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4456 KB Output is correct
2 Partially correct 31 ms 4464 KB Partially correct
3 Partially correct 36 ms 4596 KB Partially correct
4 Correct 19 ms 2752 KB Output is correct
5 Partially correct 28 ms 3924 KB Partially correct
6 Correct 19 ms 3740 KB Output is correct
7 Correct 19 ms 3628 KB Output is correct
8 Correct 19 ms 3304 KB Output is correct
9 Correct 17 ms 3268 KB Output is correct
10 Correct 21 ms 2996 KB Output is correct
11 Correct 18 ms 3024 KB Output is correct
12 Correct 16 ms 2760 KB Output is correct
13 Partially correct 17 ms 2760 KB Partially correct
14 Correct 17 ms 2756 KB Output is correct
15 Correct 22 ms 2872 KB Output is correct
16 Correct 24 ms 2872 KB Output is correct
17 Correct 19 ms 2936 KB Output is correct
18 Correct 19 ms 2992 KB Output is correct
19 Correct 25 ms 3132 KB Output is correct
20 Incorrect 19 ms 3780 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4584 KB Output is correct
2 Correct 34 ms 4584 KB Output is correct
3 Incorrect 40 ms 4904 KB Output isn't correct
4 Halted 0 ms 0 KB -