oj.uz

Submission #601060

# Submission time Handle Problem Language Result Execution time Memory
601060 2022-07-21T10:44:39 Z TimDee Stranded Far From Home (BOI22_island) C++17
10 / 100
 416 ms 26444 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 (u<v) continue;
        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 0 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 214 ms 476 KB Output is correct
5 Correct 230 ms 468 KB Output is correct
6 Correct 269 ms 468 KB Output is correct
7 Correct 214 ms 448 KB Output is correct
8 Correct 152 ms 460 KB Output is correct
9 Correct 416 ms 500 KB Output is correct
10 Correct 105 ms 448 KB Output is correct
11 Correct 101 ms 440 KB Output is correct
12 Correct 115 ms 468 KB Output is correct
13 Correct 183 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 131 ms 26444 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 21 ms 3428 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 20 ms 3356 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.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 Correct 0 ms 212 KB Output is correct
4 Correct 214 ms 476 KB Output is correct
5 Correct 230 ms 468 KB Output is correct
6 Correct 269 ms 468 KB Output is correct
7 Correct 214 ms 448 KB Output is correct
8 Correct 152 ms 460 KB Output is correct
9 Correct 416 ms 500 KB Output is correct
10 Correct 105 ms 448 KB Output is correct
11 Correct 101 ms 440 KB Output is correct
12 Correct 115 ms 468 KB Output is correct
13 Correct 183 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 131 ms 26444 KB Output isn't correct
18 Halted 0 ms 0 KB -