Submission #829410

#	Time	Username	Problem	Language	Result	Execution time	Memory
829410		QwertyPi	Stranded Far From Home (BOI22_island)	C++14	100 / 100	338 ms	72420 KiB

island

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

const int N = 2e5 + 11;
const int LGN = 20;
int a[N], p[N];

struct edge{
	int u, v;
};

struct DSU{
    int dsu[N];
    void init(int n){
        for(int i = 0; i <= n; i++) dsu[i] = i;
    }
    int f(int x){ return dsu[x] == x ? x : dsu[x] = f(dsu[x]); }
    void g(int x, int y){ x = f(x); y = f(y); dsu[x] = y; }
    bool sa(int x, int y){ return f(x) == f(y); }
} dsu;

vector<int> G[N];
int st[N], bl[LGN][N];

void add_edge(int u, int v){
	G[v].push_back(u);
}

void dfs(int v, int pa = -1){
	st[v] = a[v];
	for(auto u : G[v]){
		dfs(u, v); st[v] += st[u];
	}
}

void dfs2(int v, int pa = -1){
	st[v] = a[v];
	for(auto u : G[v]){
		bl[0][u] = st[u] >= a[v] ? v : u;
		for(int j = 1; j < LGN; j++){
			bl[j][u] = bl[j - 1][bl[j - 1][u]];
		}
		dfs2(u, v);
	}
}

int32_t main(){
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<edge> E;
	vector<pair<int, int>> ord;
	for(int i = 1; i <= n; i++) ord.push_back({a[i], i});
	sort(ord.begin(), ord.end());
	for(int i = 1; i <= n; i++) p[ord[i - 1].second] = i;
	for(int i = 0; i < m; i++){
		int u, v; cin >> u >> v; if(p[u] > p[v]) swap(u, v);
		E.push_back({u, v});
	}
	sort(E.begin(), E.end(), [](edge e1, edge e2){ return p[e1.v] < p[e2.v]; });

	dsu.init(n);
	for(auto [u, v] : E){
		if(dsu.sa(u, v)) continue;
		add_edge(dsu.f(u), v); dsu.g(u, v);
	}

	int rt = dsu.f(1);
	dfs(rt); dfs2(rt);
	for(int i = 1; i <= n; i++){
		cout << (bl[LGN - 1][i] == 0 ? "1" : "0");
	}
	cout << endl;
}

Compilation message (stderr)

island.cpp: In function 'int32_t main()':
island.cpp:66:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |  for(auto [u, v] : E){
      |           ^

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