oj.uz

답안 #723125

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723125 2023-04-13T09:01:59 Z MurotY Stranded Far From Home (BOI22_island) C++14
10 / 100
 486 ms 40256 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz size()
using namespace std;
const double pi = 2 * acos(0.0);
const ll N=1e6+7, M=998244353;
vector <ll> g[N];
ll a[N], res[N];
bool u[N];
ll sum[N], ans[N];
ll dfs(int v){
    sum[v]=a[v];
    u[v]=1;
    for (auto l:g[v]){
        if (!u[l]){
            sum[v]+=dfs(l);
        }
    }
    return sum[v];
}

void dfs1(int v){
    if (sum[v] >= a[res[v]] && ans[res[v]] == ans[v]) ans[v]=1;
    else{
        if (v != 1) return ;
    }
    u[v]=1;
    for (auto l:g[v]){
        if (!u[l]){
            res[l]=v;
            dfs1(l);
        }
    }
    return ;
}
void solve()
{
	int n, m;
	cin >> n >> m;
	
	for (int i=1;i<=n;i++) cin >> a[i];
	for (int i=1;i<=m;i++){
		int x, y;
		cin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
    if (n <= 2000 && m <= 2000){
		for (int i=1;i<=n;i++){
			set <pair <ll, ll>> q;
			vector <int> u(n+5, 0);
			q.insert({0, i});
			ll sum=0, cnt=0;
			while (!q.empty()){
			    pair <ll,ll> mn=*q.begin();
			    if (sum < mn.ff) break;
			    if (u[mn.ss]) continue;
			    u[mn.ss]=1;
			    q.erase(mn);
			    sum+=a[mn.ss];
			    for (auto l:g[mn.ss]){
			        if (!u[l]) {
			            q.insert({a[l], l});
			        }
			    }
			}
			if (q.sz == 0) cout << "1";
			else cout << "0";
		}
		return ;
    }
    ans[1]=1;
    dfs(1);
    fill(u, u+n+5, 0);
    dfs1(1);
    for (int i=1;i<=n;i++) cout << ans[i] << " ";
    return;
}
int main(){
	ios;
	int t=1;	
//	cin >> t;
	while (t--){ 
	    solve();
	    cout << "\n";
	}
	return 0;
}

Compilation message

island.cpp: In function 'void solve()':
island.cpp:61:14: warning: unused variable 'cnt' [-Wunused-variable]
   61 |    ll sum=0, cnt=0;
      |              ^~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 301 ms 24012 KB Output is correct
5 Correct 276 ms 23900 KB Output is correct
6 Correct 469 ms 23908 KB Output is correct
7 Correct 297 ms 23944 KB Output is correct
8 Correct 232 ms 23908 KB Output is correct
9 Correct 486 ms 23892 KB Output is correct
10 Correct 134 ms 23900 KB Output is correct
11 Correct 126 ms 23892 KB Output is correct
12 Correct 163 ms 23912 KB Output is correct
13 Correct 284 ms 23896 KB Output is correct
14 Correct 160 ms 23900 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 14 ms 23716 KB Output is correct
3 Incorrect 137 ms 37452 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23812 KB Output is correct
2 Incorrect 131 ms 40256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 154 ms 35268 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 14 ms 23764 KB Output is correct
4 Correct 301 ms 24012 KB Output is correct
5 Correct 276 ms 23900 KB Output is correct
6 Correct 469 ms 23908 KB Output is correct
7 Correct 297 ms 23944 KB Output is correct
8 Correct 232 ms 23908 KB Output is correct
9 Correct 486 ms 23892 KB Output is correct
10 Correct 134 ms 23900 KB Output is correct
11 Correct 126 ms 23892 KB Output is correct
12 Correct 163 ms 23912 KB Output is correct
13 Correct 284 ms 23896 KB Output is correct
14 Correct 160 ms 23900 KB Output is correct
15 Correct 14 ms 23764 KB Output is correct
16 Correct 14 ms 23716 KB Output is correct
17 Incorrect 137 ms 37452 KB Output isn't correct
18 Halted 0 ms 0 KB -