oj.uz

Submission #601215

# Submission time Handle Problem Language Result Execution time Memory
601215 2022-07-21T13:18:34 Z TimDee Stranded Far From Home (BOI22_island) C++17
20 / 100
 405 ms 67356 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.upper_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.upper_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 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 206 ms 5140 KB Output is correct
5 Correct 209 ms 5136 KB Output is correct
6 Correct 260 ms 5148 KB Output is correct
7 Correct 194 ms 5148 KB Output is correct
8 Correct 149 ms 5116 KB Output is correct
9 Correct 405 ms 5180 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 106 ms 5120 KB Output is correct
12 Correct 112 ms 5148 KB Output is correct
13 Correct 175 ms 5120 KB Output is correct
14 Correct 106 ms 5128 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 28104 KB Output is correct
4 Correct 141 ms 28052 KB Output is correct
5 Correct 180 ms 21392 KB Output is correct
6 Correct 184 ms 21852 KB Output is correct
7 Correct 189 ms 21940 KB Output is correct
8 Correct 194 ms 21960 KB Output is correct
9 Correct 144 ms 23104 KB Output is correct
10 Correct 96 ms 22372 KB Output is correct
11 Correct 108 ms 22388 KB Output is correct
12 Correct 155 ms 21900 KB Output is correct
13 Correct 138 ms 36512 KB Output is correct
14 Correct 139 ms 36508 KB Output is correct
15 Correct 171 ms 36544 KB Output is correct
16 Correct 88 ms 36172 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Runtime error 183 ms 67356 KB Execution killed with signal 6
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 17084 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 2 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 206 ms 5140 KB Output is correct
5 Correct 209 ms 5136 KB Output is correct
6 Correct 260 ms 5148 KB Output is correct
7 Correct 194 ms 5148 KB Output is correct
8 Correct 149 ms 5116 KB Output is correct
9 Correct 405 ms 5180 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 106 ms 5120 KB Output is correct
12 Correct 112 ms 5148 KB Output is correct
13 Correct 175 ms 5120 KB Output is correct
14 Correct 106 ms 5128 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 28104 KB Output is correct
18 Correct 141 ms 28052 KB Output is correct
19 Correct 180 ms 21392 KB Output is correct
20 Correct 184 ms 21852 KB Output is correct
21 Correct 189 ms 21940 KB Output is correct
22 Correct 194 ms 21960 KB Output is correct
23 Correct 144 ms 23104 KB Output is correct
24 Correct 96 ms 22372 KB Output is correct
25 Correct 108 ms 22388 KB Output is correct
26 Correct 155 ms 21900 KB Output is correct
27 Correct 138 ms 36512 KB Output is correct
28 Correct 139 ms 36508 KB Output is correct
29 Correct 171 ms 36544 KB Output is correct
30 Correct 88 ms 36172 KB Output is correct
31 Correct 2 ms 4948 KB Output is correct
32 Runtime error 183 ms 67356 KB Execution killed with signal 6
33 Halted 0 ms 0 KB -