oj.uz

답안 #753916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
753916 2023-06-06T10:08:24 Z Abito Stranded Far From Home (BOI22_island) C++14
10 / 100
 1000 ms 524288 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
typedef unsigned long long ull;
using namespace std;
const int N=2e5+5;
int n,m,a[N],dis[N],par[N],dp[N];
vector<int> adj[N],v;
bool cmp(int x,int y){
    return dis[x]<dis[y];
}
void dfs(int node,int d,int p){
    dis[node]=d;
    dp[node]=a[node];
    par[node]=p;
    for (auto u:adj[node]){
        if (u==p) continue;
        dfs(u,d+1,node);
        dp[node]+=dp[u];
    }return;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    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;
        adj[x].pb(y);
        adj[y].pb(x);
    }dfs(1,0,0);
    for (int i=2;i<=n;i++) v.pb(i);
    sort(v.begin(),v.end(),cmp);
    //for (int i=1;i<=n;i++) cout<<dp[i]<<endl;
    for (auto node:v){
        if (dp[node]<a[par[node]]) continue;
        dp[node]=dp[par[node]];
    }
    for (int i=1;i<=n;i++) cout<<bool(dp[i]==dp[1]);
    return 0;
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 296 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 142 ms 27172 KB Output is correct
4 Correct 181 ms 27500 KB Output is correct
5 Correct 193 ms 20800 KB Output is correct
6 Correct 167 ms 21320 KB Output is correct
7 Correct 178 ms 21312 KB Output is correct
8 Correct 183 ms 21324 KB Output is correct
9 Correct 136 ms 22472 KB Output is correct
10 Correct 101 ms 22628 KB Output is correct
11 Correct 123 ms 22608 KB Output is correct
12 Correct 166 ms 21256 KB Output is correct
13 Correct 142 ms 35904 KB Output is correct
14 Correct 153 ms 35904 KB Output is correct
15 Correct 150 ms 35824 KB Output is correct
16 Correct 93 ms 35544 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

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

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 296 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -