oj.uz

Submission #1046899

# Submission time Handle Problem Language Result Execution time Memory
1046899 2024-08-07T06:01:25 Z tradz Plahte (COCI17_plahte) C++14
160 / 160
 139 ms 107836 KB 
#include <bits/stdc++.h>

#define For(i,a,b) for(int i = a; i <= b; i++)
#define Ford(i,a,b) for(int i = a; i >= b; i--)
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define RRH(v) v.resize(unique(all(v)) - v.begin())
#define pb push_back
#define ep emplace_back
using namespace std;
const int  N = 1e6+7;
const int M = 1e9+7;
const ll oo = 3e18;

int n, m;
struct rec {
    int x, y, u, v;
} a[N];
struct point {
    int x, y, c;
} b[N];
struct query {
    int x, t, id;
};
vector<array<int, 3>> event;
int ans[N];

vector<int> g[N];
int in[N];
int par[N];
set<pair<ii,int>> h;
set<int> color[N];
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];
}

void DFS(int u) {
    for (int v: g[u]) {
        DFS(v);
        if (color[u].size() < color[v].size()) swap(color[u], color[v]);
        for (int x: color[v]) color[u].insert(x);
    }
    ans[u] = color[u].size();
}

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

    #define TASK ""
    if (fopen (".inp", "r")) {
        freopen (".inp", "r", stdin);
        freopen (".out", "w", stdout);
    }
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }

    cin >> n >> m;
    For (i, 1, n) {
        in[i] = 0;
        auto &[x, y, u, v] = a[i];
        cin >> x >> y >> u >> v;
        event.pb({x, -1, i});
        event.pb({u, 1, i});
    }

    For (i, 1, m) {
        auto &[x, y, c] = b[i];
        cin >> x >> y >> c;
        event.pb({x, 0, i});
    }

    sort(all(event), [](array <int, 3> a, array<int, 3> b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] < b[0];
    });

    for (auto x: event) {
        if (x[1] == -1) {
            if (h.size()) par[x[2]] = parent(a[x[2]].y);
            h.insert({{a[x[2]].y, -1}, x[2]});
            h.insert({{a[x[2]].v, 1}, x[2]});
        }

        else if(x[1] == 1) {            
            h.erase({{a[x[2]].y, -1}, x[2]});
            h.erase({{a[x[2]].v, 1}, x[2]});    
        }
        else if (x[1] == 0) {
            int id = parent(b[x[2]].y);
            color[id].insert(b[x[2]].c);
        }
    }

    For (u, 1, n) {
        in[u] += par[u] != 0;
        g[par[u]].push_back(u);
    }

    For (i, 1, n) {
        if (!in[i]) DFS(i);
    }

    For (i, 1, n) cout << ans[i] << "\n";

    return 0;
}

Compilation message

plahte.cpp: In function 'int main()':
plahte.cpp:69:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         auto &[x, y, u, v] = a[i];
      |               ^
plahte.cpp:76:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |         auto &[x, y, c] = b[i];
      |               ^
plahte.cpp:58:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen (".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~
plahte.cpp:59:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen (".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
plahte.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 88008 KB Output is correct
2 Correct 48 ms 88776 KB Output is correct
3 Correct 10 ms 80476 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 90312 KB Output is correct
2 Correct 52 ms 88780 KB Output is correct
3 Correct 10 ms 80472 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 100108 KB Output is correct
2 Correct 84 ms 94660 KB Output is correct
3 Correct 11 ms 80472 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 107836 KB Output is correct
2 Correct 135 ms 101124 KB Output is correct
3 Correct 11 ms 80652 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 105156 KB Output is correct
2 Correct 121 ms 100544 KB Output is correct
3 Correct 10 ms 80472 KB Output is correct