oj.uz

Submission #854554

# Submission time Handle Problem Language Result Execution time Memory
854554 2023-09-28T03:13:36 Z wakandaaa Plahte (COCI17_plahte) C++17
160 / 160
 176 ms 47556 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define bit(x) (1 << (x))
#define file ""
using namespace std;

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
long long rand(long long l, long long r) {
    return l + rd() % (r - l + 1);
}

const int N = 2e5 + 5;
const int mod = 1e9 + 7; // 998244353;
const int inf = INT_MAX;
const long long llinf = LLONG_MAX;
const int lg = 25; // lg + 1

template<class X, class Y> bool minimize(X &a, Y b) {
    return a > b ? (a = b, true) : false;
}
template<class X, class Y> bool maximize(X &a, Y b) {
    return a < b ? (a = b, true) : false;
}
template<class X, class Y> bool add(X &a, Y b) {
    a += b;
    while (a >= mod) a -= mod;
    while (a < 0) a += mod;
    return true;
}

int n, m;

vector<int> adj[N];
int par[N];
int ans[N];

set<int> col[N];

set<int> dfs(int u, int p) {
    set<int> cur;
    for (auto i : col[u]) cur.insert(i);

    for (int v : adj[u]) if (v != p) {
        auto nxt = dfs(v, u);
        if ((int) nxt.size() > (int) cur.size()) swap(nxt, cur);
        for (auto i : nxt) cur.insert(i);
    }
    ans[u] = cur.size();
    return cur;
}

// typedef
#define OPEN -1
#define CLOSE 1
#define POINT 0

typedef tuple<int, int, int> event;

vector<event> events; // [x, type, id]
set<event> s; // [y, type, id]

struct archi {
    int x, y, u, v;
} a[N];

struct point {
    int x, y, c;
} b[N];

int idx[N];

int getpar(int y) {
    auto it = s.lower_bound({y, 0, 0});
    if (it == s.end()) return 0;
    int type = get<1>(*it);
    int id = get<2>(*it);
    if (type == OPEN) return par[id];
    return id;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    // freopen(file".inp", "r",stdin);
    // freopen(file".out", "w",stdout);

    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        a[i] = {x, y, u, v};
        events.push_back({x, -1, i});
        events.push_back({u, 1, i});
    }   

    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        cin >> x >> y >> c;
        b[i] = {x, y, c};
        events.push_back({x, 0, i});
    }

    sort(all(events));

    for (auto [x, type, id] : events) {
        if (type == OPEN) {
            par[id] = getpar(a[id].y);
            s.insert({a[id].y, -1, id});
            s.insert({a[id].v, 1, id});
        }

        if (type == POINT) {
            idx[id] = getpar(b[id].y);
            col[idx[id]].insert(b[id].c);
        }

        if (type == CLOSE) {
            s.erase({a[id].y, -1, id});
            s.erase({a[id].v, 1, id});
        }
    }

    for (int i = 1; i <= n; ++i) {
        adj[i].push_back(par[i]);
        adj[par[i]].push_back(i);
    }

    dfs(0, -1);

    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << '\n';
    }

    return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 27328 KB Output is correct
2 Correct 49 ms 27452 KB Output is correct
3 Correct 4 ms 22108 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 30476 KB Output is correct
2 Correct 64 ms 28872 KB Output is correct
3 Correct 4 ms 22104 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 39276 KB Output is correct
2 Correct 104 ms 33192 KB Output is correct
3 Correct 4 ms 22104 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 47556 KB Output is correct
2 Correct 159 ms 36540 KB Output is correct
3 Correct 4 ms 22108 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 43964 KB Output is correct
2 Correct 169 ms 37396 KB Output is correct
3 Correct 4 ms 22104 KB Output is correct