제출 #602596

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602596		TimDee	Stranded Far From Home (BOI22_island)	C++17	35 / 100	1095 ms	49852 KiB

island

#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;
        }

    }

};

struct BIT {
    vector<int> bit;  // binary indexed tree
    int n;
 
    BIT(int n) {
        this->n = n;
        bit.assign(n, 0);
    }
 
    BIT(vector<int> a) : BIT(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
 
    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
 
    int sum(int l, int r) {
        if (l>r) return -1;
        return sum(r) - sum(l - 1);
    }
 
    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

BIT ft(0);
indextree st(0);

void rec3(string&ans, int l, int r) {
    if (l==r) {ans[l]='1'; return;}
    if (l>r) return;

    int m=st.query(l,r+1);
    ans[m]='1';

    if (ft.sum(l,m-1)>=a[m]) rec3(ans,l,m-1);
    if (ft.sum(m+1,r)>=a[m]) rec3(ans,m+1,r);
}

void subtask3(int n, int m) {
    string ans(n,'0');
    a.push_back(-1e9);
    BIT jopa(a);
    ft=jopa;
    indextree Paiu(a);
    st=Paiu;
    rec3(ans,0,n-1);
    cout<<ans;
}

vector<int> dif;
vector<int> vis, genvis;
map<int,vector<int>> mp;

void rec4(vector<int> s, string&ans) {

    //cout<<"set:\n"; for (auto i:s) cout<<i<<' '; cout<<'\n';

    int mx=0;
    for (auto i:s) mx=max(mx,a[i]);
    vector<int> src; for (auto i:s) if (a[i]==mx) src.pb(i);
    for (auto i:src) genvis[i]=1;
    vis=genvis;
    //cout<<mx<<'\n';

    for (auto u:src) {
        //cout<<"from "<<u<<"\n";
        for (auto x:adj[u]) {

            if (vis[x]) continue;

            vector<int> news = {x};
            queue<int> q;
            int sum=0;
            q.push(x); vis[x]=1;
            while (!q.empty()) {
                int u=q.front(); q.pop();
                sum+=a[u];
                for (auto v:adj[u]) {
                    if (!vis[v]) {
                        vis[v]=1;
                        q.push(v);
                        news.pb(v);
                    }
                }
            }

            //cout<<"subset:\n"; for (auto i:news) cout<<i<<' '; cout<<'\n';
            //cout<<sum<<'\n';

            if (sum>=a[u]) rec4(news,ans);
            else {
                for (auto i:news) { genvis[i]=1; ans[i]='0'; }
            }

        }
    }    

}

void subtask4(int n, int m) {
    string ans(n,'1');
    sort(rall(dif));
    genvis.assign(n,0);
    forn(i,n) mp[a[i]].pb(i);
    vector<int> myset; forn(i,n) myset.pb(i);
    rec4(myset,ans);
    cout<<ans<<'\n';
}

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;
    }

    map<int,int> cnt; int diff=0;
    forn(i,n) {if (!cnt[a[i]]) dif.pb(a[i]); diff+=((cnt[a[i]]++)==0); }
    if (diff<=10) {
        subtask4(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
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 30
• Subtask 5: 0 / 35