oj.uz

Submission #601222

# Submission time Handle Problem Language Result Execution time Memory
601222 2022-07-21T13:20:51 Z TimDee Stranded Far From Home (BOI22_island) C++17
20 / 100
 1000 ms 429984 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;
        if (left.find(u)!=left.end()) 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 4 ms 4948 KB Output is correct
2 Correct 4 ms 4916 KB Output is correct
3 Correct 4 ms 4976 KB Output is correct
4 Correct 230 ms 5148 KB Output is correct
5 Correct 240 ms 5132 KB Output is correct
6 Correct 321 ms 5128 KB Output is correct
7 Correct 217 ms 5140 KB Output is correct
8 Correct 162 ms 5124 KB Output is correct
9 Correct 470 ms 5176 KB Output is correct
10 Correct 117 ms 5128 KB Output is correct
11 Correct 107 ms 5076 KB Output is correct
12 Correct 142 ms 5144 KB Output is correct
13 Correct 189 ms 5124 KB Output is correct
14 Correct 127 ms 5132 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 3 ms 4948 KB Output is correct
3 Correct 184 ms 28088 KB Output is correct
4 Correct 141 ms 28032 KB Output is correct
5 Correct 230 ms 21328 KB Output is correct
6 Correct 201 ms 21852 KB Output is correct
7 Correct 192 ms 21904 KB Output is correct
8 Correct 211 ms 21920 KB Output is correct
9 Correct 185 ms 23188 KB Output is correct
10 Correct 100 ms 22444 KB Output is correct
11 Correct 124 ms 22324 KB Output is correct
12 Correct 203 ms 21940 KB Output is correct
13 Correct 171 ms 36516 KB Output is correct
14 Correct 138 ms 36516 KB Output is correct
15 Correct 197 ms 36428 KB Output is correct
16 Correct 103 ms 36120 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 1111 ms 429984 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 142 ms 16844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Correct 4 ms 4916 KB Output is correct
3 Correct 4 ms 4976 KB Output is correct
4 Correct 230 ms 5148 KB Output is correct
5 Correct 240 ms 5132 KB Output is correct
6 Correct 321 ms 5128 KB Output is correct
7 Correct 217 ms 5140 KB Output is correct
8 Correct 162 ms 5124 KB Output is correct
9 Correct 470 ms 5176 KB Output is correct
10 Correct 117 ms 5128 KB Output is correct
11 Correct 107 ms 5076 KB Output is correct
12 Correct 142 ms 5144 KB Output is correct
13 Correct 189 ms 5124 KB Output is correct
14 Correct 127 ms 5132 KB Output is correct
15 Correct 3 ms 4948 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 184 ms 28088 KB Output is correct
18 Correct 141 ms 28032 KB Output is correct
19 Correct 230 ms 21328 KB Output is correct
20 Correct 201 ms 21852 KB Output is correct
21 Correct 192 ms 21904 KB Output is correct
22 Correct 211 ms 21920 KB Output is correct
23 Correct 185 ms 23188 KB Output is correct
24 Correct 100 ms 22444 KB Output is correct
25 Correct 124 ms 22324 KB Output is correct
26 Correct 203 ms 21940 KB Output is correct
27 Correct 171 ms 36516 KB Output is correct
28 Correct 138 ms 36516 KB Output is correct
29 Correct 197 ms 36428 KB Output is correct
30 Correct 103 ms 36120 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Execution timed out 1111 ms 429984 KB Time limit exceeded
33 Halted 0 ms 0 KB -