oj.uz

Submission #601067

# Submission time Handle Problem Language Result Execution time Memory
601067 2022-07-21T10:52:14 Z TimDee Stranded Far From Home (BOI22_island) C++17
20 / 100
 414 ms 38532 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]; //cout<<v<<' '<<d[v]<<' '<<a[v]<<'\n';
    for (auto u:adj[v]) {
        dfs(adj,vis,d,u);
        if (u>v) 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;
    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,vis,d,0);
    //forn(i,n) cout<<d[i]<<' '; cout<<'\n';
    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 211 ms 456 KB Output is correct
5 Correct 207 ms 468 KB Output is correct
6 Correct 262 ms 468 KB Output is correct
7 Correct 195 ms 448 KB Output is correct
8 Correct 145 ms 340 KB Output is correct
9 Correct 414 ms 504 KB Output is correct
10 Correct 109 ms 448 KB Output is correct
11 Correct 99 ms 440 KB Output is correct
12 Correct 115 ms 468 KB Output is correct
13 Correct 188 ms 340 KB Output is correct
14 Correct 104 ms 468 KB Output is correct

Subtask #2
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 143 ms 26436 KB Output is correct
4 Correct 140 ms 28216 KB Output is correct
5 Correct 170 ms 21240 KB Output is correct
6 Correct 175 ms 22236 KB Output is correct
7 Correct 169 ms 23004 KB Output is correct
8 Correct 200 ms 22996 KB Output is correct
9 Correct 135 ms 23940 KB Output is correct
10 Correct 93 ms 23880 KB Output is correct
11 Correct 100 ms 23672 KB Output is correct
12 Correct 164 ms 22424 KB Output is correct
13 Correct 127 ms 36156 KB Output is correct
14 Correct 127 ms 37336 KB Output is correct
15 Correct 159 ms 38532 KB Output is correct
16 Correct 91 ms 37268 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 18 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 19 ms 3424 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 211 ms 456 KB Output is correct
5 Correct 207 ms 468 KB Output is correct
6 Correct 262 ms 468 KB Output is correct
7 Correct 195 ms 448 KB Output is correct
8 Correct 145 ms 340 KB Output is correct
9 Correct 414 ms 504 KB Output is correct
10 Correct 109 ms 448 KB Output is correct
11 Correct 99 ms 440 KB Output is correct
12 Correct 115 ms 468 KB Output is correct
13 Correct 188 ms 340 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 Correct 143 ms 26436 KB Output is correct
18 Correct 140 ms 28216 KB Output is correct
19 Correct 170 ms 21240 KB Output is correct
20 Correct 175 ms 22236 KB Output is correct
21 Correct 169 ms 23004 KB Output is correct
22 Correct 200 ms 22996 KB Output is correct
23 Correct 135 ms 23940 KB Output is correct
24 Correct 93 ms 23880 KB Output is correct
25 Correct 100 ms 23672 KB Output is correct
26 Correct 164 ms 22424 KB Output is correct
27 Correct 127 ms 36156 KB Output is correct
28 Correct 127 ms 37336 KB Output is correct
29 Correct 159 ms 38532 KB Output is correct
30 Correct 91 ms 37268 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Incorrect 18 ms 3428 KB Output isn't correct
33 Halted 0 ms 0 KB -