oj.uz

Submission #601055

# Submission time Handle Problem Language Result Execution time Memory
601055 2022-07-21T10:40:42 Z TimDee Stranded Far From Home (BOI22_island) C++17
10 / 100
 427 ms 28080 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define paiu return
#define moment 0;
 
#define int long long
#define double long double
#define ll long long

#define forr(i,x) for (int i=0; i<x; i++)
#define forn(i,x) for (int i=0; i<x; i++)

#define vi(a,n) vector<int> a(n,0)
 
//cringe define
#define vii(a,n) vi(a,n); forr(i,n) cin>>a[i];
vector<int> ___makeprefsum(vector<int>&a) {
    int n=a.size();
    vi(pr,n+1);
    forn(i,n) pr[i+1]=pr[i]+a[i];
    return pr;
}
#define prefsum(pr,a) vector<int> pr=___makeprefsum(a);
 
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
 
#define pb(x) push_back(x)
#define pf pop_front();
#define last(c) c[c.size()-1]
 
#define f first
#define s second
 
#define pi pair<int, int>
#define mp(x,y) make_pair(x, y)
 
const ll mod = 1000000007;
const double ppi = acos(0) * 2;
     
const int maxn = 1e5+1;
const int inf = INT_MAX;
const ll linf = LLONG_MAX;
const ll mmod = 998244353;

vector<int> a;
auto cmp = [](int i, int j) { return a[i]<=a[j]; };

void subtask1(int n, int m) {
    vii(b,n); a=b;
    vector<vector<int>> adj(n);
    forn(i,m) {
        int u,v; cin>>u>>v;
        --u, --v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    string ans(n,'1');

    forn(i,n) {
        set<int,decltype(cmp)> s(cmp);
        int cnt=a[i];
        bitset<2000> vis; vis.set(i,1); //cout<<i+1<<"->";
        for (auto v:adj[i]) { s.insert(v); vis.set(v,1); }
        while (!s.empty()) {
            auto it=s.begin();
            int u=*it;
            //cout<<u+1<<"->";
            if (a[u]>cnt) {ans[i]='0'; break;}
            cnt+=a[u]; 
            vis.set(u,1);
            s.erase(it);
            for (auto v:adj[u]) if (!vis[v]) { s.insert(v); vis.set(v,1); }
        }
        //cout<<'\n';
    }
    cout<<ans;
}

void dfs(vector<vector<int>>&adj, vector<int>&vis, vector<int>&d, int v) {
    if (vis[v]) return;
    vis[v]=1;
    d[v]+=a[v];
    for (auto u:adj[v]) {
        dfs(adj,vis,d,u);
        d[v]+=d[u];
    }
}

void ver(vector<vector<int>>&adj, vector<int>&vis, vector<int>&d, vector<int>&up, int v) {
    if (vis[v]) return;
    if (!up[v]) return;
    vis[v]=1;
    for (auto u:adj[v]) {
        if (d[u]>=a[v]) up[u]=1;
        ver(adj,vis,d,up,u);
    }
}

void subtask2(int n, int m) {
    vector<vector<int>> adj(n);
    vector<int> up(n,0);
    forn(i,m) {
        int u,v; cin>>u>>v;
        --u, --v;
        if (u>v) swap(u,v);
        up[v]=u;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    vector<int> d(n,0), vis(n,0);
    dfs(adj,d,vis,0);
    up[0]=1;
    vis.assign(n,0);
    ver(adj,vis,d,up,0);
    forn(i,n) cout<<up[i];
}

void solve() {
    
    int n,m; cin>>n>>m;
    if (n<=2000 && m<=2000) {
        subtask1(n,m);
        return;
    } 
    vii(b,n); a=b;
    int foo=1;
    forn(i,n-1) foo&=(a[i]>=a[i+1]);
    if (foo) {
        subtask2(n,m);
    }
    
}

int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int t=1;
    //cin>>t;
    while(t--) solve();
    
    paiu moment
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 214 ms 488 KB Output is correct
5 Correct 220 ms 468 KB Output is correct
6 Correct 284 ms 588 KB Output is correct
7 Correct 202 ms 468 KB Output is correct
8 Correct 145 ms 468 KB Output is correct
9 Correct 427 ms 520 KB Output is correct
10 Correct 104 ms 476 KB Output is correct
11 Correct 104 ms 480 KB Output is correct
12 Correct 126 ms 500 KB Output is correct
13 Correct 205 ms 588 KB Output is correct
14 Correct 105 ms 472 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 143 ms 28080 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 27 ms 3944 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 23 ms 3916 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 214 ms 488 KB Output is correct
5 Correct 220 ms 468 KB Output is correct
6 Correct 284 ms 588 KB Output is correct
7 Correct 202 ms 468 KB Output is correct
8 Correct 145 ms 468 KB Output is correct
9 Correct 427 ms 520 KB Output is correct
10 Correct 104 ms 476 KB Output is correct
11 Correct 104 ms 480 KB Output is correct
12 Correct 126 ms 500 KB Output is correct
13 Correct 205 ms 588 KB Output is correct
14 Correct 105 ms 472 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 143 ms 28080 KB Output isn't correct
18 Halted 0 ms 0 KB -