oj.uz

Submission #601217

# Submission time Handle Problem Language Result Execution time Memory
601217 2022-07-21T13:19:33 Z TimDee Stranded Far From Home (BOI22_island) C++17
20 / 100
 451 ms 36428 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;
vector<vector<int>> adj(2e5);
auto cmp = [](int i, int j) { return a[i]<=a[j]; };

void subtask1(int n, int m) {

    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<<'\n';
}

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<int> up(n,0);
    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]; cout<<'\n';
}

int n;  // array size
vector<int> t;

int merge(int i, int j) {
    if (a[i]<=a[j]) return i;
    else return j;
}

void build(int _n) {  // build the tree
    a.push_back(linf);
    n=_n;
  for (int i = n - 1; i > 0; --i) t[i] = merge ( t[i<<1] , t[i<<1|1] );
}

void modify(int p, int value) {  // set value at position p
  for (t[p += n] = value; p > 1; p >>= 1) t[p>>1] = merge( t[p] , t[p^1] );
}

void subtask3(int n, int m) {
    string ans(n,'1');
    set<int> left;
    forn(i,n) left.insert(i);
    t.assign(2*2e5,n);
    forn(i,n) t[n+i]=i;
    build(n);
    int unvis=n;
    vector<int> d(n,0), vis(n,0);
    forn(i,n) d[i]=a[i];
    while (unvis) {
        int u=t[1]; --unvis;
        if (u==n) break;
        //left.erase(left.find(u));
        vector<int> path = {u};
        auto it1=left.lower_bound(u), it2=left.upper_bound(u);
        d.push_back(linf);
        int l=n,r=n;
        if (it1!=left.begin()) {--it1; 
            l=*it1; 
        }
        if (it2!=left.end()) {
            r=*it2;
        }

        while (l!=n || r!=n) {
            int v;
            if (d[l]<=d[r]) v=l;
            else v=r;
            if (a[u]>a[l] && a[u]>a[r]) break;
            else if (a[u]>a[v]) v = (v==l)?r:l;
            if (v==n) {
                for (auto x:path) { modify(x,n); }
                --unvis;
                break;
            }
            if (d[u]>=a[v]) {
                left.erase(left.find(v));
                if (v<u) {
                    auto it1=left.lower_bound(u);
                    if (it1!=left.begin()) {
                        --it1; 
                        l=*it1; 
                    } else l=n;
                } else {
                    auto it2=left.upper_bound(u);
                    if (it2!=left.end()) {
                        r=*it2;
                    } else r=n;
                }
                --unvis;
            } else {
                for (auto x:path) { ans[x]='0'; modify(x,n); }
                d[v]+=d[u];
                break;
            }
            d[v]+=d[u];
            u=v;
            path.pb(v);
        }

    }
    cout<<ans;
}

void solve() {
    
    int n,m; cin>>n>>m;
    vii(b,n); a=b;
    int _p3=1, _p2=1;
    vector<int> lesscnt(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);
        _p3&=(abs(u-v)==1);
        lesscnt[max(u,v)]++;
    }

    forn(i,n) _p2&=(i==0 || (lesscnt[i]==1));

    if (n<=2000 && m<=2000) {
        subtask1(n,m);
        return;
    } 
    forn(i,n-1) _p2&=(a[i]>=a[i+1]);
    if (_p2) {
        subtask2(n,m);
        return;
    }
    if (_p3) {
        subtask3(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
}

Compilation message

island.cpp: In function 'void subtask2(long long int, long long int)':
island.cpp:12:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   12 | #define forn(i,x) for (int i=0; i<x; i++)
      |                   ^~~
island.cpp:105:5: note: in expansion of macro 'forn'
  105 |     forn(i,n) cout<<up[i]; cout<<'\n';
      |     ^~~~
island.cpp:105:28: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  105 |     forn(i,n) cout<<up[i]; cout<<'\n';
      |                            ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 221 ms 5132 KB Output is correct
5 Correct 248 ms 5148 KB Output is correct
6 Correct 283 ms 5132 KB Output is correct
7 Correct 217 ms 5152 KB Output is correct
8 Correct 176 ms 5124 KB Output is correct
9 Correct 451 ms 5180 KB Output is correct
10 Correct 101 ms 5076 KB Output is correct
11 Correct 134 ms 5120 KB Output is correct
12 Correct 124 ms 5148 KB Output is correct
13 Correct 190 ms 5076 KB Output is correct
14 Correct 118 ms 5132 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 185 ms 28012 KB Output is correct
4 Correct 153 ms 28020 KB Output is correct
5 Correct 211 ms 21356 KB Output is correct
6 Correct 207 ms 21860 KB Output is correct
7 Correct 194 ms 21908 KB Output is correct
8 Correct 198 ms 21952 KB Output is correct
9 Correct 220 ms 23116 KB Output is correct
10 Correct 102 ms 22440 KB Output is correct
11 Correct 158 ms 22376 KB Output is correct
12 Correct 185 ms 21940 KB Output is correct
13 Correct 196 ms 36404 KB Output is correct
14 Correct 149 ms 36408 KB Output is correct
15 Correct 175 ms 36428 KB Output is correct
16 Correct 96 ms 36104 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 200 ms 34956 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 Incorrect 133 ms 17032 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 221 ms 5132 KB Output is correct
5 Correct 248 ms 5148 KB Output is correct
6 Correct 283 ms 5132 KB Output is correct
7 Correct 217 ms 5152 KB Output is correct
8 Correct 176 ms 5124 KB Output is correct
9 Correct 451 ms 5180 KB Output is correct
10 Correct 101 ms 5076 KB Output is correct
11 Correct 134 ms 5120 KB Output is correct
12 Correct 124 ms 5148 KB Output is correct
13 Correct 190 ms 5076 KB Output is correct
14 Correct 118 ms 5132 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 185 ms 28012 KB Output is correct
18 Correct 153 ms 28020 KB Output is correct
19 Correct 211 ms 21356 KB Output is correct
20 Correct 207 ms 21860 KB Output is correct
21 Correct 194 ms 21908 KB Output is correct
22 Correct 198 ms 21952 KB Output is correct
23 Correct 220 ms 23116 KB Output is correct
24 Correct 102 ms 22440 KB Output is correct
25 Correct 158 ms 22376 KB Output is correct
26 Correct 185 ms 21940 KB Output is correct
27 Correct 196 ms 36404 KB Output is correct
28 Correct 149 ms 36408 KB Output is correct
29 Correct 175 ms 36428 KB Output is correct
30 Correct 96 ms 36104 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Incorrect 200 ms 34956 KB Output isn't correct
33 Halted 0 ms 0 KB -