제출 #1112941

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1112941		Art	Colors (RMI18_colors)	C++17	100 / 100	479 ms	91700 KiB

colors

// Art - Bùi Hải Đăng k65
// Keep typing, keep loving

// #pragma GCC optimize("02,unroll-loops")
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, n)       for (int i = 0, _n = (n); i < _n; ++i)

#define __Art__         int main()

const int N = 2e5 + 10;

using namespace std;

int t, n, m, a[N], b[N];
vector<int> adjA[N], adjB[N];
vector<pair<int, int>> edges;

struct DisjointSet {
    struct node {
        int x, y, xSize, ySize;
    };
    stack<node> st;
    int par[2 * N], sz[2 * N];

    void makeSet() {
        FOR (i, 1, 2e5) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int findSet(int v) {
        return v == par[v] ? v : findSet(par[v]);
    }

    void unionSet(int a, int b) {
        a = findSet(a);
        b = findSet(b);
        if (a != b) {
            if (sz[a] < sz[b]) {
                swap(a, b);
            }

            st.push({a, b, sz[a], sz[b]});
            sz[a] += sz[b];
            par[b] = a;
        }
    }

    void rollBack(int SZ) {
        while ((int)st.size() > SZ) {
            node top = st.top();
            st.pop();
            par[top.x] = top.x;
            par[top.y] = top.y;
            sz[top.x] = top.xSize;
            sz[top.y] = top.ySize;
        }
    }
} dsu;

struct SegmenTree {
    int res;
    vector<pair<int, int>> st[4 * N];

    void update(int id, int l, int r, int u, int v, pair<int, int> edge) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            st[id].emplace_back(edge);
            return;
        }

        int m = (l + r) / 2;
        update(id * 2, l, m, u, v, edge);
        update(id * 2 + 1, m + 1, r, u, v, edge);
    }

    void solve(int id, int l, int r) {
        int sz = (int)dsu.st.size();
        for (auto [u, v] : st[id]) {
            dsu.unionSet(u, v);
        }
        if (l == r) {
            unordered_set<int> cnt;
            for (auto x : adjA[l]) cnt.insert(dsu.findSet(x));
            for (auto x : adjB[l]) if (!cnt.count(dsu.findSet(x))) {
                res = 0;
            }
        } 
        else {
            int m = (l + r) / 2;
            solve(id * 2, l, m);
            solve(id * 2 + 1, m + 1, r);
        }
        dsu.rollBack(sz);
    }
} seg;

// ---------------------------- //
// time limit: 3s
// memory limit: 256mb
__Art__ {

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

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

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

    dsu.makeSet();

    int numTest;
    cin >> numTest;
    while (numTest--) {
        cin >> n >> m;
        edges.clear();
        FOR (i, 1, n) {
            adjA[i].clear();
            adjB[i].clear();
        }
        FOR (i, 1, 4 * n) {
            seg.st[i].clear();
        }
        FOR (i, 1, n) {
            cin >> a[i];
            adjA[a[i]].emplace_back(i);
        }
        FOR (i, 1, n) {
            cin >> b[i];
            adjB[b[i]].emplace_back(i);
        }
        FOR (i, 1, m) {
            int u, v; cin >> u >> v;
            edges.emplace_back(u, v);
        }

        seg.res = 1;
        bool check = 0;
        FOR (i, 1, n) if (a[i] < b[i]) {
            seg.res = 0; check = 1; break;
        }
        if (check) {
            cout << seg.res, el; continue;
        }
        for (auto [u, v] : edges) {
            int mn = max(b[u], b[v]);
            int mx = min(a[u], a[v]);
            if (mn <= mx) {
                // cout << mn << ' ' << mx, el;
                seg.update(1, 1, n, mn, mx, {u, v});
            }
        }

        seg.solve(1, 1, n);
        cout << seg.res, el;
    }

    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

colors.cpp: In function 'int main()':
colors.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen("art.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
colors.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen("art.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
colors.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen("colors.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
colors.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen("colors.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 7 / 7
• Subtask 3: 8 / 8
• Subtask 4: 15 / 15
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 10 / 10
• Subtask 8: 22 / 22