제출 #602596

#제출 시각아이디문제언어결과실행 시간메모리
602596TimDeeStranded Far From Home (BOI22_island)C++17
35 / 100
1095 ms49852 KiB
#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';
      |                                                                                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...