Submission #601296

#	Time	Username	Problem	Language	Result	Execution time	Memory
601296		patrikpavic2	Stranded Far From Home (BOI22_island)	C++17	0 / 100	228 ms	31284 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] = 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){
		//printf("%d -> %d\n", x, par[x]);
		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;
}

Compilation message (stderr)

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

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