oj.uz

답안 #987303

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
987303 2024-05-22T14:20:30 Z crafticat The Potion of Great Power (CEOI20_potion) C++17
56 / 100
 1560 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

using pii = pair<int,int>;
vector<pii> roads;
int n, d, u, q;
constexpr int inf = 1e9 + 7;
constexpr int none = 1e9;
vector<int> h;
vector<map<int, int>> to, from;

struct Node {
    Node *left = nullptr, *right = nullptr;
    int l, r, mid, exists = 0, id = 0, realL, realR;

    Node(int l, int r, int id) : l(l) ,r(r),id(id) ,mid((r + l) / 2) {
        realL = from[id][l];
        realR = from[id][r];
    }

    void push() {
        if (r - l > 1) {
            if (!left) left = new Node(l,mid,id);
            if (!right) right = new Node(mid,r,id);
        }
    }
};

Node* ins(int x, Node* node, int newX, int id) {
    if (node->r - node->l <= 1) {
        Node* z = new Node(node->l,node->r,id);
        z->exists = node->exists;
        z->exists += newX;
        return z;
    }

    node->push();
    Node* z = new Node(node->l,node->r,id);

    if (x < node->mid) {
        z->left = ins(x,node->left,newX,id);
        z->right = node->right;
    } else {
        z->right = ins(x,node->right,newX,id);
        z->left = node->left;
    }
    z->exists = z->left->exists + z->right->exists;
    return z;
}

Node* addEdge(vector<set<pii>> &g, int a, int b, vector<Node*> &lastNodes) {
    pii p = {h[b],b};
    if (g[a].count(p)) {
        g[a].erase(p);
        return ins(to[a][p.first],lastNodes[a],-1,a);
    }
    else {
        g[a].insert(p);
        return ins(to[a][p.first],lastNodes[a],true,a);
    }
}

int closest(Node* node, int x) {
    if (!node) return inf;
    if (node->exists == 0) return inf;
    if (node->r - node->l <= 1 && node->exists > 0) return abs(x - node->realL);
    if (node->realL <= x && node->realR >= x) {
        return min(closest(node->left, x), closest(node->right, x));
    }

    if (node->realL >= x && node->left && node->left->exists > 0) return closest(node->left, x);
    else {
        if (node->right && node->right->exists > 0)
            return closest(node->right, x);
        else
            return closest(node->left, x);
    }
}

void dfs(Node* x, vector<int> &dfsData) {
    if (x == nullptr) return;
    if (x->r - x->l <= 1) {
        dfsData.push_back(x->l);
        return;
    }
    if (x->left && x->left->exists> 0) dfs(x->left,dfsData);
    if (x->right && x->right->exists>0) dfs(x->right,dfsData);
}
vector<int> getDfs(Node* d) {
    vector<int> ans;
    dfs(d,ans);
    return ans;
}

vector<map<int,Node*>> nodes;
void init(int N, int D, int H[]) {
    n = N;
    d = D;
    h.resize(n + 1);
    for (int i = 0; i < n; ++i) {
        h[i] = H[i];
    }

}

void curseChanges(int U, int A[], int B[]) {
    vector<set<int>> ex(n);
    vector<int> siz(n);

    u = U;
    for (int i = 0; i < u; ++i) {
        int a = A[i], b = B[i];
        roads.emplace_back(a,b);
        ex[a].insert(h[b]);
        ex[b].insert(h[a]);
    }
    from.resize(n);
    to.resize(n);
    for (int i = 0; i < n; ++i) {
        int genId =0;
        for (auto v : ex[i]) {
            to[i][v] = genId;
            from[i][genId++] = v;
        }
        siz[i] = genId;
        to[i][inf] = genId;
        from[i][genId++] = inf;
    }

    // Time, Node* (Upper bound time)
    nodes.resize(n + 1);
    vector<Node*> lastNodes(n + 1);
    for (int i = 0; i < n; ++i) {
        lastNodes[i] = new Node(0,siz[i],i);
        nodes[i].insert({0, lastNodes[i]});
    }
    vector<set<pii>> g(n + 1);
    for (int i = 0; i < u; ++i) {
        auto [a,b] = roads[i];
        lastNodes[a] = addEdge(g,a,b,lastNodes);
        lastNodes[b] = addEdge(g,b,a,lastNodes);
        nodes[a].insert({-i - 1, lastNodes[a]});
        nodes[b].insert({-i -1, lastNodes[b]});
    }
}

int question(int a, int b, int t) {
    auto itB = nodes[b].lower_bound(-t);
    auto itA = nodes[a].lower_bound(-t);
    Node* nodeB = itB->second, *nodeA = itA->second;

    if (nodeB->exists < nodeA->exists) {
        swap(a,b);
        swap(nodeA,nodeB);
    } // A is smaller
    if (nodeB->exists == 0 || nodeA->exists == 0) {
        return none;
    }

    int ans = 1e9;
    for (auto x : getDfs(nodeA)) {
        ans = min(ans, closest(nodeB,from[a][x]));
    }
    return ans;
}

Compilation message

potion.cpp: In constructor 'Node::Node(int, int, int)':
potion.cpp:15:32: warning: 'Node::id' will be initialized after [-Wreorder]
   15 |     int l, r, mid, exists = 0, id = 0, realL, realR;
      |                                ^~
potion.cpp:15:15: warning:   'int Node::mid' [-Wreorder]
   15 |     int l, r, mid, exists = 0, id = 0, realL, realR;
      |               ^~~
potion.cpp:17:5: warning:   when initialized here [-Wreorder]
   17 |     Node(int l, int r, int id) : l(l) ,r(r),id(id) ,mid((r + l) / 2) {
      |     ^~~~

Subtask #1
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1624 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 3 ms 1880 KB Output is correct
4 Correct 52 ms 48404 KB Output is correct

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1006 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1253 ms 175224 KB Output is correct
2 Correct 557 ms 124008 KB Output is correct
3 Correct 926 ms 134140 KB Output is correct
4 Correct 877 ms 133992 KB Output is correct
5 Correct 988 ms 173636 KB Output is correct
6 Correct 906 ms 134112 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 14936 KB Output is correct
2 Correct 136 ms 16208 KB Output is correct
3 Correct 239 ms 12368 KB Output is correct
4 Correct 1560 ms 15956 KB Output is correct
5 Correct 1274 ms 16208 KB Output is correct
6 Correct 213 ms 15104 KB Output is correct
7 Correct 1260 ms 13904 KB Output is correct

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 1624 KB Output is correct
3 Correct 3 ms 1868 KB Output is correct
4 Correct 3 ms 1880 KB Output is correct
5 Correct 52 ms 48404 KB Output is correct
6 Runtime error 1006 ms 262144 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -