oj.uz

Submission #877003

# Submission time Handle Problem Language Result Execution time Memory
877003 2023-11-22T16:43:29 Z phongcd Plahte (COCI17_plahte) C++14
160 / 160
 171 ms 36560 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long  double
#define ull unsigned long long
#define ii pair <int, int>
#define ill pair <ll, ll>
#define ild pair <ld, ld>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define file "test"
using namespace std;
const int N = 1e5 + 2;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
const ll base = 311;
const int BLOCK_SIZE = 400;

int n, m;
int par[N], in[N], ans[N];
vector <int> adj[N];
set <int> g[N];
set <pair <ii, int>> h;

int parent(int v) {
    auto it = h.lower_bound({{v, 0}, 0});
    if (it == h.end()) return 0;
    int t = (*it).fi.se, id = (*it).se;
    if (t == 1) return id;
    return par[id];
}

set <int> dfs(int u, int p) {
    set <int> res;
    for (int k: g[u]) res.insert(k);

    for (int v: adj[u]) if (v != p) {
        set <int> tmp = dfs(v, u);
        if (res.size() < tmp.size()) swap(res, tmp);
        for (int k: tmp) res.insert(k);
    }
    ans[u] = res.size();
    return res;
}

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

    cin >> n >> m;
    vector <pair <ii, ii>> rec;
    vector <pair <ii, int>> event, ball;
    for (int i = 0; i < n; i ++) {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        rec.push_back({{x, y}, {u, v}});
        event.push_back({{x, -1}, i});
        event.push_back({{u, 1}, i});
    }

    for (int i = 0; i < m; i ++) {
        int x, y, k;
        cin >> x >> y >> k;
        ball.push_back({{x, y}, k});
        event.push_back({{x, 0}, i});
    }

    sort(all(event));

    for (pair <ii, int> e: event) {
        auto [x, t] = e.fi;
        int i = e.se;
        if (t == -1) {
            if (!h.empty())
                par[i + 1] = parent(rec[i].fi.se);
            h.insert({{rec[i].fi.se, -1}, i + 1});
            h.insert({{rec[i].se.se, 1}, i + 1});
        }
        else if (t == 1) {
            h.erase({{rec[i].fi.se, -1}, i + 1});
            h.erase({{rec[i].se.se, 1}, i + 1});
        }
        else if (!h.empty()) {
            int id = parent(ball[i].fi.se);
            g[id].insert(ball[i].se);
        }
    }

    for (int u = 1; u <= n; u ++) {
        in[u] += par[u] != 0;
        adj[u].push_back(par[u]);
        adj[par[u]].push_back(u);
    }

    for (int u = 1; u <= n; u ++)
        if (!in[u]) dfs(u, 0);

    for (int i = 1; i <= n; i ++)
        cout << ans[i] << '\n';
}
/*
     /\_/\ zzZ
    (= -_-)
    / >u  >u
*/

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:70:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   70 |         auto [x, t] = e.fi;
      |              ^

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 13656 KB Output is correct
2 Correct 50 ms 13492 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 17188 KB Output is correct
2 Correct 56 ms 15224 KB Output is correct
3 Correct 2 ms 7512 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 25752 KB Output is correct
2 Correct 96 ms 19456 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 36560 KB Output is correct
2 Correct 162 ms 25664 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 33192 KB Output is correct
2 Correct 152 ms 26436 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct