oj.uz

답안 #107123

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
107123 2019-04-22T05:29:00 Z szawinis Amusement Park (JOI17_amusement_park) C++17
0 / 100
 45 ms 4768 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) {
    pre[u] = ++tick;
    for(int v: g[u]) {
        if(pre[v]) continue;
        dfs(v, g, pre, tick);
    }
}

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);
    for(int i = 0; i < n; i++) {
        MessageBoard(i, X >> ((pre[i] - 1) % 61) & 1);
    }
}

#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 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());

//    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 = V << pre[P] % 61;
    int curr = P;
    for(int step = 1; step < 61; step++) {
        int pos = (pre[P] + step) % 61;
        int nxt = rev[pre[P] + step < n ? pre[P] + step : (pre[P] + step) % 61];
        assert(0 <= curr && curr < n && 0 <= nxt && nxt < n && curr != nxt);
//        cerr << "Ioi_iterate " << curr << ' ' << nxt << ' ' << pos << endl;
        ret += moveToNext(curr, nxt, d, par) << pos;
        curr = nxt;
    }
    return ret;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 864 KB Output is correct
2 Correct 5 ms 896 KB Output is correct
3 Correct 4 ms 772 KB Output is correct
4 Correct 4 ms 768 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Incorrect 5 ms 676 KB Wrong Answer [7]
7 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 4328 KB Output is correct
2 Correct 32 ms 4328 KB Output is correct
3 Incorrect 36 ms 4332 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 776 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 7 ms 1560 KB Output is correct
5 Incorrect 6 ms 1436 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 4464 KB Output is correct
2 Partially correct 31 ms 4524 KB Partially correct
3 Partially correct 27 ms 4328 KB Partially correct
4 Correct 18 ms 2756 KB Output is correct
5 Incorrect 24 ms 3988 KB Wrong Answer [7]
6 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 4312 KB Output is correct
2 Incorrect 38 ms 4768 KB Wrong Answer [7]
3 Halted 0 ms 0 KB -