oj.uz

Submission #753916

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory Grader output
1 Runtime error 296 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -