제출 #601301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
601301		patrikpavic2	Stranded Far From Home (BOI22_island)	C++17	100 / 100	305 ms	43284 KiB

island

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

#define X first
#define Y second
#define PB push_back

using namespace std;

typedef vector < int > vi;
typedef long long ll;

const int N = 2e5 + 500;

vector < int > v[N], rd, T[N];
int n, m, vel[N], bio[N], jed[N];
int par[N], naj[N], dobar[N], ppar[N];
ll sm[N];

int pr_jed(int x){
	if(jed[x] == x) return x;
	return jed[x] = pr_jed(jed[x]);
}

int pr(int x){
	if(x == ppar[x]) return x;
	return ppar[x] = pr(ppar[x]);
}

bool cmp_vel(int A, int B){
	return vel[A] < vel[B];
}

void dfs(int x){
	for(int y : T[x]){
		dfs(y); 
		sm[x] += sm[y];
	}
	sm[x] += vel[x];
}


int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i++){
		scanf("%d", vel + i), rd.PB(i);
		jed[i] = i; ppar[i] = i;
	}
	for(int i = 0;i < m;i++){
		int a, b; scanf("%d%d", &a, &b);
		v[a].PB(b), v[b].PB(a);	
	}
	sort(rd.begin(), rd.end(), cmp_vel);
	for(int x : rd){
		bio[x] = 1;
		for(int y : v[x]){
			if(!bio[y]) continue;
			T[x].PB(pr(y));
		}
		sort(T[x].begin(), T[x].end());
		T[x].erase(unique(T[x].begin(), T[x].end()), T[x].end());
		for(int y : T[x]){
			if(vel[y] == vel[x]) 
				jed[pr_jed(y)] = pr_jed(x);
			par[y] = x; ppar[y] = x;
		}
	}
	reverse(rd.begin(), rd.end());
	dfs(rd[0]);
	for(int x : rd){
		if(!par[x] || (dobar[pr_jed(par[x])] && sm[x] >= vel[par[x]]))
			dobar[x] = 1;
	}
	for(int i = 1;i <= n;i++)
		printf("%d", dobar[pr_jed(i)]);
	printf("\n");
	return 0;
}

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

island.cpp: In function 'int main()':
island.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
island.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   scanf("%d", vel + i), rd.PB(i);
      |   ~~~~~^~~~~~~~~~~~~~~
island.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~

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