oj.uz

Submission #601169

# Submission time Handle Problem Language Result Execution time Memory
601169 2022-07-21T12:19:11 Z TimDee Stranded Far From Home (BOI22_island) C++17
20 / 100
 405 ms 36520 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;
        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 (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;
                }
                u=v;
                --unvis;
            } else {
                for (auto x:path) { ans[x]='0'; modify(x,n); }
                d[v]+=d[u];
                break;
            }
            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';
      |                            ^~~~

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 209 ms 5136 KB Output is correct
5 Correct 207 ms 5132 KB Output is correct
6 Correct 266 ms 5196 KB Output is correct
7 Correct 197 ms 5156 KB Output is correct
8 Correct 143 ms 5076 KB Output is correct
9 Correct 405 ms 5196 KB Output is correct
10 Correct 100 ms 5116 KB Output is correct
11 Correct 98 ms 5128 KB Output is correct
12 Correct 115 ms 5148 KB Output is correct
13 Correct 180 ms 5124 KB Output is correct
14 Correct 106 ms 5076 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 156 ms 28020 KB Output is correct
4 Correct 134 ms 28108 KB Output is correct
5 Correct 176 ms 21348 KB Output is correct
6 Correct 177 ms 21872 KB Output is correct
7 Correct 180 ms 21892 KB Output is correct
8 Correct 192 ms 21932 KB Output is correct
9 Correct 142 ms 23236 KB Output is correct
10 Correct 95 ms 22428 KB Output is correct
11 Correct 98 ms 22452 KB Output is correct
12 Correct 151 ms 21932 KB Output is correct
13 Correct 131 ms 36520 KB Output is correct
14 Correct 129 ms 36488 KB Output is correct
15 Correct 165 ms 36464 KB Output is correct
16 Correct 86 ms 36132 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 Incorrect 249 ms 34044 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 115 ms 16992 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 209 ms 5136 KB Output is correct
5 Correct 207 ms 5132 KB Output is correct
6 Correct 266 ms 5196 KB Output is correct
7 Correct 197 ms 5156 KB Output is correct
8 Correct 143 ms 5076 KB Output is correct
9 Correct 405 ms 5196 KB Output is correct
10 Correct 100 ms 5116 KB Output is correct
11 Correct 98 ms 5128 KB Output is correct
12 Correct 115 ms 5148 KB Output is correct
13 Correct 180 ms 5124 KB Output is correct
14 Correct 106 ms 5076 KB Output is correct
15 Correct 2 ms 4948 KB Output is correct
16 Correct 2 ms 4948 KB Output is correct
17 Correct 156 ms 28020 KB Output is correct
18 Correct 134 ms 28108 KB Output is correct
19 Correct 176 ms 21348 KB Output is correct
20 Correct 177 ms 21872 KB Output is correct
21 Correct 180 ms 21892 KB Output is correct
22 Correct 192 ms 21932 KB Output is correct
23 Correct 142 ms 23236 KB Output is correct
24 Correct 95 ms 22428 KB Output is correct
25 Correct 98 ms 22452 KB Output is correct
26 Correct 151 ms 21932 KB Output is correct
27 Correct 131 ms 36520 KB Output is correct
28 Correct 129 ms 36488 KB Output is correct
29 Correct 165 ms 36464 KB Output is correct
30 Correct 86 ms 36132 KB Output is correct
31 Correct 2 ms 4948 KB Output is correct
32 Incorrect 249 ms 34044 KB Output isn't correct
33 Halted 0 ms 0 KB -