Submission #1351244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1351244		top1svtin	Stranded Far From Home (BOI22_island)	C++17	0 / 100	357 ms	79684 KiB

island

#include <bits/stdc++.h>

#define kien long long
#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 task "a"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back

using namespace std;
const int mxn = 2e5 + 5;
kien n, m, a[mxn];
kien ans[mxn];
vector <int> dp[mxn];
map <kien, vector <kien>> pp;
map <kien, vector <kien>> ver;

struct DSU {
    kien par[mxn], sum[mxn], sz[mxn];
    void init(int n) {
        FOR (i, 1, n) par[i] = i, sum[i] = a[i], sz[i] = 1;
    }

    int find_set (int u) {
        return par[u] == u ? u : par[u] = find_set(par[u]);
    }

    void union_set (int u, int v) {
        u = find_set(u); v = find_set(v);
        if (u == v) return;
//        if (sz[u] < sz[v]) swap(u, v);
        sum[u] += sum[v];
        sz[u] += sz[v];
        par[v] = u;
    }

    int get (int u) {
        u = find_set(u); return sum[u];
    }

    int kich (int u) {
        u = find_set(u); return sz[u];
    }
} dsu;

main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen(task".inp", "r")) {
        fin(task); fou(task);
    }
    cin >> n >> m;
    FOR (i, 1, n) { cin >> a[i]; pp[a[i]].pb(i); ver[a[i]].pb(i); ans[i] = 1; }
    FOR (i, 1, m) {
        int u, v;
        cin >> u >> v;
        dp[u].pb(v); dp[v].pb(u);
    }
    dsu.init(n);

    for (auto i : pp) {
//        dsu.init(n);
        for (auto u : ver[i.first]) {
            for (auto v : dp[u]) {
                /// ta có thể rút gọn a[u] <= a[v] vì u luôn thuộc ver[i.first] tức là u luôn == i.first
                if (a[v] <= a[u]) { dsu.union_set(u, v); }
            }
        }

        for (auto x : i.second) {
//            cout << x << " ";
            kien tong = dsu.get(x);
//            cout << tong << " " << i.first << "\n";
            if (tong > i.first) pp[tong].pb(x);
            else if (dsu.kich(x) != n) {
                ans[x] = 0;
            }
        }
    }

    FOR (i, 1, n) cout << ans[i];
}

Compilation message (stderr)

island.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main() {
      | ^~~~
island.cpp: In function 'int main()':
island.cpp:7:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | #define fin(x) freopen(x".inp","r",stdin)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
island.cpp:51:9: note: in expansion of macro 'fin'
   51 |         fin(task); fou(task);
      |         ^~~
island.cpp:8:23: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fou(x) freopen(x".out","w",stdout)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~~
island.cpp:51:20: note: in expansion of macro 'fou'
   51 |         fin(task); fou(task);
      |                    ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35