oj.uz

Submission #601296

# Submission time Handle Problem Language Result Execution time Memory
601296 2022-07-21T15:44:41 Z patrikpavic2 Stranded Far From Home (BOI22_island) C++17
0 / 100
 228 ms 31284 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 169 ms 31284 KB Output is correct
4 Incorrect 197 ms 27080 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 215 ms 25628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Incorrect 228 ms 25552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9684 KB Output is correct
2 Correct 7 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Incorrect 6 ms 9796 KB Output isn't correct
5 Halted 0 ms 0 KB -