oj.uz

답안 #593600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
593600 2022-07-11T12:26:19 Z Blagojce Stranded Far From Home (BOI22_island) C++11
10 / 100
 1000 ms 408660 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;


const int mxn = 2e5 + 5;

int n, m;
vector<int> g[mxn];
ll a[mxn];

vector<int> S[mxn];
vector<int> G[mxn];



ll sum[mxn];

int v_count = 0;
int vis_ver[mxn];
int vis_edg[mxn];

vector<int> merge(int u, int v){
	vector<int> cand;
	for(auto vp : S[v]){
		if(vis_ver[vp] == v_count) continue;
		
		S[u].pb(vp);
		sum[u] += a[vp];
		vis_ver[vp] = v_count;
	}
	for(auto ep : G[v]){
		if(vis_edg[ep] == v_count || vis_ver[ep] == v_count) continue;
		G[u].pb(ep);
		cand.pb(ep);
		vis_edg[ep] = v_count;
	}
	return cand;
}

void expand(int u){
	++v_count;
	for(auto e : S[u]) vis_ver[e] = v_count;
	for(auto e : G[u]) vis_edg[e] = v_count;
	
	pq <pair<int,int> > Q;
	for(auto e : G[u]) Q.push({-a[e], e});
	
	while(!Q.empty()){
		int c = Q.top().nd;
		Q.pop();
		if(vis_ver[c] == v_count) continue;
		if(sum[u] < a[c]) continue;
		vector<int> cand = merge(u, c);
		for(auto c : cand){
			Q.push({-a[c], c});
		}
	}
}

int main(){
	cin >> n >> m;
	fr(i, 0, n){
		cin >> a[i];
	}
	fr(i, 0, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		g[u].pb(v);
		g[v].pb(u);
	}
	fr(i, 0, n){
		G[i] = g[i];
		S[i] = {i};
		sum[i] = a[i];
	}
	fr(i, 0, n){
		expand(i);
	}
	fr(i, 0, n){
		if(S[i].size() > n) cout<<2/0<<endl;
		if((int)S[i].size() == n) cout<<1;
		else cout<<0;
	}
	
}

Compilation message

island.cpp: In function 'int main()':
island.cpp:91:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   91 |   if(S[i].size() > n) cout<<2/0<<endl;
      |      ~~~~~~~~~~~~^~~
island.cpp:91:30: warning: division by zero [-Wdiv-by-zero]
   91 |   if(S[i].size() > n) cout<<2/0<<endl;
      |                             ~^~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 10 ms 14388 KB Output is correct
3 Correct 8 ms 14408 KB Output is correct
4 Correct 29 ms 22740 KB Output is correct
5 Correct 32 ms 23144 KB Output is correct
6 Correct 137 ms 30856 KB Output is correct
7 Correct 31 ms 22540 KB Output is correct
8 Correct 27 ms 21204 KB Output is correct
9 Correct 265 ms 40604 KB Output is correct
10 Correct 32 ms 23640 KB Output is correct
11 Correct 34 ms 23156 KB Output is correct
12 Correct 29 ms 21788 KB Output is correct
13 Correct 156 ms 40940 KB Output is correct
14 Correct 27 ms 22168 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14408 KB Output is correct
3 Execution timed out 1012 ms 97648 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Execution timed out 1047 ms 408660 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Execution timed out 1061 ms 176044 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 14420 KB Output is correct
2 Correct 10 ms 14388 KB Output is correct
3 Correct 8 ms 14408 KB Output is correct
4 Correct 29 ms 22740 KB Output is correct
5 Correct 32 ms 23144 KB Output is correct
6 Correct 137 ms 30856 KB Output is correct
7 Correct 31 ms 22540 KB Output is correct
8 Correct 27 ms 21204 KB Output is correct
9 Correct 265 ms 40604 KB Output is correct
10 Correct 32 ms 23640 KB Output is correct
11 Correct 34 ms 23156 KB Output is correct
12 Correct 29 ms 21788 KB Output is correct
13 Correct 156 ms 40940 KB Output is correct
14 Correct 27 ms 22168 KB Output is correct
15 Correct 8 ms 14420 KB Output is correct
16 Correct 9 ms 14408 KB Output is correct
17 Execution timed out 1012 ms 97648 KB Time limit exceeded
18 Halted 0 ms 0 KB -