oj.uz

Submission #601213

# Submission time Handle Problem Language Result Execution time Memory
601213 2022-07-21T13:14:49 Z TimDee Stranded Far From Home (BOI22_island) C++17
20 / 100
 457 ms 67424 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*n,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 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 236 ms 5132 KB Output is correct
5 Correct 218 ms 5136 KB Output is correct
6 Correct 298 ms 5136 KB Output is correct
7 Correct 198 ms 5140 KB Output is correct
8 Correct 146 ms 5124 KB Output is correct
9 Correct 457 ms 5196 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 94 ms 5120 KB Output is correct
12 Correct 114 ms 5152 KB Output is correct
13 Correct 201 ms 5116 KB Output is correct
14 Correct 106 ms 5136 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 28064 KB Output is correct
4 Correct 154 ms 28040 KB Output is correct
5 Correct 190 ms 21352 KB Output is correct
6 Correct 246 ms 21816 KB Output is correct
7 Correct 187 ms 21884 KB Output is correct
8 Correct 202 ms 21948 KB Output is correct
9 Correct 162 ms 23096 KB Output is correct
10 Correct 109 ms 22444 KB Output is correct
11 Correct 102 ms 22332 KB Output is correct
12 Correct 170 ms 22032 KB Output is correct
13 Correct 159 ms 36460 KB Output is correct
14 Correct 144 ms 36540 KB Output is correct
15 Correct 175 ms 36476 KB Output is correct
16 Correct 103 ms 36092 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 Runtime error 193 ms 67424 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 127 ms 16868 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 4 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 236 ms 5132 KB Output is correct
5 Correct 218 ms 5136 KB Output is correct
6 Correct 298 ms 5136 KB Output is correct
7 Correct 198 ms 5140 KB Output is correct
8 Correct 146 ms 5124 KB Output is correct
9 Correct 457 ms 5196 KB Output is correct
10 Correct 99 ms 5076 KB Output is correct
11 Correct 94 ms 5120 KB Output is correct
12 Correct 114 ms 5152 KB Output is correct
13 Correct 201 ms 5116 KB Output is correct
14 Correct 106 ms 5136 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 28064 KB Output is correct
18 Correct 154 ms 28040 KB Output is correct
19 Correct 190 ms 21352 KB Output is correct
20 Correct 246 ms 21816 KB Output is correct
21 Correct 187 ms 21884 KB Output is correct
22 Correct 202 ms 21948 KB Output is correct
23 Correct 162 ms 23096 KB Output is correct
24 Correct 109 ms 22444 KB Output is correct
25 Correct 102 ms 22332 KB Output is correct
26 Correct 170 ms 22032 KB Output is correct
27 Correct 159 ms 36460 KB Output is correct
28 Correct 144 ms 36540 KB Output is correct
29 Correct 175 ms 36476 KB Output is correct
30 Correct 103 ms 36092 KB Output is correct
31 Correct 3 ms 4948 KB Output is correct
32 Runtime error 193 ms 67424 KB Execution killed with signal 6
33 Halted 0 ms 0 KB -