oj.uz

Submission #873909

# Submission time Handle Problem Language Result Execution time Memory
873909 2023-11-16T02:41:08 Z noiaint Plahte (COCI17_plahte) C++17
160 / 160
 171 ms 48676 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 27584 KB Output is correct
2 Correct 48 ms 27576 KB Output is correct
3 Correct 4 ms 22104 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 30760 KB Output is correct
2 Correct 58 ms 28824 KB Output is correct
3 Correct 4 ms 22108 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 39104 KB Output is correct
2 Correct 93 ms 32808 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 171 ms 48676 KB Output is correct
2 Correct 155 ms 37268 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 160 ms 44992 KB Output is correct
2 Correct 148 ms 38212 KB Output is correct
3 Correct 4 ms 22108 KB Output is correct