oj.uz

Submission #601056

# Submission time Handle Problem Language Result Execution time Memory
601056 2022-07-21T10:42:03 Z TimDee Stranded Far From Home (BOI22_island) C++17
10 / 100
 425 ms 26452 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);
        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);
        return;
    }
    
}

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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 218 ms 468 KB Output is correct
5 Correct 215 ms 468 KB Output is correct
6 Correct 270 ms 444 KB Output is correct
7 Correct 200 ms 468 KB Output is correct
8 Correct 154 ms 436 KB Output is correct
9 Correct 425 ms 516 KB Output is correct
10 Correct 98 ms 340 KB Output is correct
11 Correct 94 ms 340 KB Output is correct
12 Correct 123 ms 472 KB Output is correct
13 Correct 175 ms 444 KB Output is correct
14 Correct 104 ms 468 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 152 ms 26452 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 21 ms 3412 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 218 ms 468 KB Output is correct
5 Correct 215 ms 468 KB Output is correct
6 Correct 270 ms 444 KB Output is correct
7 Correct 200 ms 468 KB Output is correct
8 Correct 154 ms 436 KB Output is correct
9 Correct 425 ms 516 KB Output is correct
10 Correct 98 ms 340 KB Output is correct
11 Correct 94 ms 340 KB Output is correct
12 Correct 123 ms 472 KB Output is correct
13 Correct 175 ms 444 KB Output is correct
14 Correct 104 ms 468 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Incorrect 152 ms 26452 KB Output isn't correct
18 Halted 0 ms 0 KB -