제출 #1127011

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127011		MinhKien	Plahte (COCI17_plahte)	C++20	0 / 160	2118 ms	554988 KiB

plahte

#include <algorithm>
#include <iostream>
#include <vector>
#include <stack>
#include <set>

#define ii pair <int, int>
#define iii pair <ii, int>
#define fi first
#define se second
using namespace std;

const int N = 2e5 + 10;

int n, m, ans[N];
set <int> s[N];
vector <int> v[N];
bool IsRoot[N];

struct rect {
    int x1, y1, x2, y2;
    int id, k;

    void input(int i) {
        if (i <= n) {
            cin >> x1 >> y1 >> x2 >> y2;
            k = -1;
        } else {
            cin >> x1 >> y1 >> k;
            x2 = x1;
            y2 = y1;
        }
        id = i;
    }

    void output() {
        cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
    }

    bool in (int l, int r, int u) {
        return u >= l && u <= r;
    }

    bool rect_in (rect o) {
        return in(x1, x2, o.x1) && in(x1, x2, o.x2) && in(y1, y2, o.y1) && in(y1, y2, o.y2);
    }
} a[N];

bool cmp (rect x, rect y) {
    return x.rect_in(y);
}

void DFS(int u) {
    if (a[u].k != -1) {
        s[u].insert(a[u].k);
    }

    for (int z: v[u]) {
        DFS(z);
        if (s[u].size() > s[z].size()) s[u].swap(s[z]);
        for (int j: s[z]) s[u].insert(j);
    }

    ans[a[u].id] = s[u].size();
}

int main() {
    // freopen("coci.inp", "r", stdin);
    // freopen("coci.out", "w", stdout);

    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    cin >> n >> m;
    for (int i = 1; i <= n + m; ++i) {
        a[i].input(i);
        IsRoot[i] = true;
    }

    for (int i = 1; i <= n + m; ++i) {
        for (int j = 1; j <= n + m; ++j) {
            if (i == j) continue;
            if (a[i].rect_in(a[j])) {
                v[i].push_back(j);
                IsRoot[j] = false;
            }
        }
    }

    for (int i = 1; i <= n + m; ++i) {
        if (IsRoot[i]) {
            DFS(i);
        }
    }

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

    return 0;
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32