제출 #702211

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702211		lovrot	Stranded Far From Home (BOI22_island)	C++17	25 / 100	195 ms	24700 KiB

island

#include <vector>
#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define pb push_back

using namespace std; 

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 

const int N = 2e5 + 10; 

int n, m, to[N], U[N], sol[N];
ll S[N], SUM[N];

vector<int> g[N]; 
vector<pair<ll, int>> p; 

int Find(int u) {
	if(u == U[u]) return u; 
	return U[u] = Find(U[u]); 
}

void Union(int u, int v) {
	v = Find(v); 
	U[v] = u; 
	SUM[u] += SUM[v]; 
	if(!to[v] || S[to[v]] == S[v]) to[v] = u; 
}

int main() {
	for(int i = 0; i < N; i++) U[i] = i;

	scanf("%d%d", &n, &m); 

	for(int i = 1; i <= n; i++) {
		scanf("%lld", S + i); 
		p.pb({S[i], i}); 
	}

	sort(p.begin(), p.end()); 

	for(int i = 0; i < m; i++) {
		int u, v; 
		scanf("%d%d", &u, &v); 
		if(S[u] < S[v] || S[u] == S[v] && u < v) swap(u, v);
		g[u].pb(v); 
	}

	for(pair<ll, int> u : p) {
		SUM[u.Y] = S[u.Y]; 
		for(int v : g[u.Y]) Union(u.Y, v); 
	}

	reverse(p.begin(), p.end()); 
	to[p[0].Y] = 0; 
	SUM[0] = 0; 
	sol[0] = 1;

	for(pair<ll, int> u : p)
		if(sol[to[u.Y]] && SUM[u.Y] >= S[to[u.Y]]) sol[u.Y] = true; 

	for(int i = 1; i <= n; i++) printf("%d", sol[i]); 
	printf("\n");
	return 0;
}

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

island.cpp: In function 'int main()':
island.cpp:50:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   50 |   if(S[u] < S[v] || S[u] == S[v] && u < v) swap(u, v);
      |                     ~~~~~~~~~~~~~^~~~~~~~
island.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%lld", S + i);
      |   ~~~~~^~~~~~~~~~~~~~~
island.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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