oj.uz

Submission #601129

# Submission time Handle Problem Language Result Execution time Memory
601129 2022-07-21T11:47:52 Z TimDee Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 36840 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';
}

struct indextree {

    vector<int> tree;
    int size;
    vector<int> a;
    int n;

    void put(int i, int v) {

        tree[i]=v;

    }

    int combine(int i, int j) {
        // for min
        if (a[i]<a[j]) return i;
        else return j;

        // for max
        //if (a[i]>a[j]) return i;
        //else return j;
    }

    void update(int v, int l, int r) {

        if (r-l==1) return;

        int mid=(l+r)/2;

        update(2*v+1,l,mid);
        update(2*v+2,mid,r);

        tree[v]=combine(tree[2*v+1],tree[2*v+2]);

    }

    void update(int v, int l, int r, int i) {

        if (r-l==1) return;
        if (r<=i || l>i) return;

        int mid=(l+r)/2;

        update(2*v+1,l,mid);
        update(2*v+2,mid,r);

        tree[v]=combine(tree[2*v+1],tree[2*v+2]);

    }

    indextree(vector<int>&arr) {
        a=arr;

        //for min
        a.pb(linf);
        //for max
        //a.pb(-linf);

        n=a.size()-1;

        size=1;
        while (size<n+1) size*=2;

        tree.assign(2*size-1, n);

        forn(i,n) put(size-1+i,i);

        update(0,0,size);

    }

    indextree(int N) {

        n=N;

        //for min
        a.assign(n+1,linf);
        //for max
        //a.assign(n+1,-linf);

        size=1;
        while (size<n+1) size*=2;

        tree.assign(2*size-1, n);
        forn(i,N) put(size-1+i,i);
        update(0,0,size);

    }

    int query(int v, int lx, int rx, int l, int r) {

        if (lx>=r || rx<=l) return n;
        if (lx>=l && rx<=r) return tree[v];

        int mid=(lx+rx)/2;

        int L = query(2*v+1,lx,mid,l,r);
        int R = query(2*v+2,mid,rx,l,r);

        return combine(L,R);

    }

    int query(int l, int r) {
        return query(0,0,size,l,r);
    }

    void set(int i, int v) {

        a[i]=v;
        update(0,0,size,i);

    }

    //MY
    void print() {

        int z=0;
        while (z<2*size-1) {
            for (int i=z; i<2*z+1; i++) cout<<"("<<tree[i]<<","<<a[tree[i]]<<") "; cout<<'\n';
            z=2*z+1;
        }

    }

};
void subtask3(int n, int m) {
    string ans(n,'1');
    set<int> left;
    forn(i,n) left.insert(i);
    indextree st(a);
    int unvis=n;
    vector<int> d(n,0), vis(n,0);
    forn(i,n) d[i]=a[i];
    while (unvis) {
        int u=st.tree[0]; --unvis;
        left.erase(left.find(u));
        vector<int> path = {u};
        set<int,decltype(cmp)> s(cmp);
        auto it1=left.upper_bound(u), it2=left.upper_bound(u);
        if (it1!=left.begin()) {--it1; 
            int l=*it1; 
            s.insert(l); 
        }
        if (it2!=left.end()) {
            int r=*it2; s.insert(r);
        }

        while (!s.empty()) {
            auto it=s.begin();
            int v=*it;
            left.erase(left.find(v));
            s.erase(it);
            if (d[u]>=d[v]) {
                if (v<u) {
                    auto it1=left.upper_bound(u);
                    if (it1!=left.begin()) {
                        --it1; 
                        int l=*it1; 
                        s.insert(l); 
                    }
                } else {
                    auto it2=left.upper_bound(u);
                    if (it2!=left.end()) {
                        int r=*it2; s.insert(r);
                    }
                }
                u=v;
                --unvis;
            } else {
                left.insert(v);
                for (auto x:path) { ans[x]='0'; st.set(x,linf); }
            }
            d[v]+=d[u];
            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';
      |                            ^~~~
island.cpp: In member function 'void indextree::print()':
island.cpp:227:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  227 |             for (int i=z; i<2*z+1; i++) cout<<"("<<tree[i]<<","<<a[tree[i]]<<") "; cout<<'\n';
      |             ^~~
island.cpp:227:84: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  227 |             for (int i=z; i<2*z+1; i++) cout<<"("<<tree[i]<<","<<a[tree[i]]<<") "; cout<<'\n';
      |                                                                                    ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 228 ms 5156 KB Output is correct
5 Correct 259 ms 5152 KB Output is correct
6 Correct 286 ms 5076 KB Output is correct
7 Correct 226 ms 5176 KB Output is correct
8 Correct 170 ms 5140 KB Output is correct
9 Correct 470 ms 5204 KB Output is correct
10 Correct 118 ms 5156 KB Output is correct
11 Correct 124 ms 5196 KB Output is correct
12 Correct 128 ms 5176 KB Output is correct
13 Correct 184 ms 5140 KB Output is correct
14 Correct 114 ms 5156 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 167 ms 28824 KB Output is correct
4 Correct 138 ms 28424 KB Output is correct
5 Correct 267 ms 21708 KB Output is correct
6 Correct 221 ms 22344 KB Output is correct
7 Correct 191 ms 22336 KB Output is correct
8 Correct 229 ms 22376 KB Output is correct
9 Correct 157 ms 23532 KB Output is correct
10 Correct 105 ms 22708 KB Output is correct
11 Correct 119 ms 22812 KB Output is correct
12 Correct 177 ms 22344 KB Output is correct
13 Correct 145 ms 36840 KB Output is correct
14 Correct 163 ms 36808 KB Output is correct
15 Correct 191 ms 36832 KB Output is correct
16 Correct 103 ms 36452 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 Execution timed out 1073 ms 35080 KB Time limit exceeded
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 131 ms 17720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 228 ms 5156 KB Output is correct
5 Correct 259 ms 5152 KB Output is correct
6 Correct 286 ms 5076 KB Output is correct
7 Correct 226 ms 5176 KB Output is correct
8 Correct 170 ms 5140 KB Output is correct
9 Correct 470 ms 5204 KB Output is correct
10 Correct 118 ms 5156 KB Output is correct
11 Correct 124 ms 5196 KB Output is correct
12 Correct 128 ms 5176 KB Output is correct
13 Correct 184 ms 5140 KB Output is correct
14 Correct 114 ms 5156 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 167 ms 28824 KB Output is correct
18 Correct 138 ms 28424 KB Output is correct
19 Correct 267 ms 21708 KB Output is correct
20 Correct 221 ms 22344 KB Output is correct
21 Correct 191 ms 22336 KB Output is correct
22 Correct 229 ms 22376 KB Output is correct
23 Correct 157 ms 23532 KB Output is correct
24 Correct 105 ms 22708 KB Output is correct
25 Correct 119 ms 22812 KB Output is correct
26 Correct 177 ms 22344 KB Output is correct
27 Correct 145 ms 36840 KB Output is correct
28 Correct 163 ms 36808 KB Output is correct
29 Correct 191 ms 36832 KB Output is correct
30 Correct 103 ms 36452 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Execution timed out 1073 ms 35080 KB Time limit exceeded
33 Halted 0 ms 0 KB -