제출 #207458

#제출 시각아이디문제언어결과실행 시간메모리
207458SegtreeCollapse (JOI18_collapse)C++14
100 / 100
12608 ms74136 KiB
#include<iostream> #include<algorithm> #include<vector> #include<queue> #include<set> #include<unordered_set> #include<unordered_map> #include"collapse.h" using namespace std; typedef long long ll; typedef pair<ll,ll> pll; typedef vector<int> vi; #define chmin(a,b) a=min(a,b) #define chmax(a,b) a=max(a,b) #define all(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<n;i++) #define mod 1000000007 #define mad(a,b) a=(a+b)%mod #pragma gcc optimize("O3") #pragma gcc optimize("unroll-loops") #pragma gcc target("avx2,see4") #define Nmax 100010 #define B 300 namespace uf{ ll p[Nmax],uni; void init(){ rep(i,Nmax)p[i]=i; uni=0; } ll par(ll x){ return p[x]=(x==p[x]?x:par(p[x])); } void unite(ll a,ll b){ a=par(a),b=par(b); if(a!=b){ p[a]=b; uni++; } } }; typedef struct query{ ll w,p,id; }query; bool comp_w(const query&a,const query&b){ return a.w<b.w; } bool comp_p(const query&a,const query&b){ return a.p<b.p; } vector<query> qrys[Nmax]; bool vis[Nmax]; vector<ll> graph[Nmax]; ll cmp[Nmax]; void dfs(ll x,ll cmps){ if(vis[x])return; vis[x]=1; if(cmps>=0)cmp[x]=cmps; for(auto y:graph[x])dfs(y,cmps); } typedef struct edge{ ll x,y; }edge; bool edge_comp_x(const edge&a,const edge&b){ return a.x>b.x; } bool edge_comp_y(const edge&a,const edge&b){ return a.y<b.y; } vi simulateCollapse(int N,vi T,vi X,vi Y,vi W,vi P){ for(int i=0;i<Nmax;i++){ qrys[i].clear(); graph[i].clear(); } for(int i=0;i<T.size();i++){ if(X[i]>Y[i])swap(X[i],Y[i]); //subtask2限定 //if(X[i]<=P[0]&&P[0]+1<=Y[i])X[i]=Y[i]=0; } vi fans(W.size()); for(int i=0;i<W.size();i++){ qrys[W[i]].push_back((query){W[i],P[i],i}); fans[i]=0; } for(int L=0;L<T.size();L+=B){ int R=min(L+B,(int)T.size()); vector<edge> baseedge; //{//base,s,baseedgeを用意 unordered_set<ll> base,s; for(int i=0;i<L;i++){ ll has=(ll)X[i]*Nmax+Y[i]; if(base.count(has))base.erase(has); else base.insert(has); } for(int i=L;i<R;i++){ ll has=(ll)X[i]*Nmax+Y[i]; if(base.count(has)){ base.erase(has); s.insert(has); } } for(auto e:base){ ll x=e/Nmax,y=e%Nmax; baseedge.push_back((edge){x,y}); } /*for(int i=0;i<N;i++){vis[i]=0;graph[i].clear();} for(auto e:base){ ll x=e/Nmax,y=e%Nmax; graph[x].push_back(y); graph[y].push_back(x); } ll basecmp=0; for(int i=0;i<N;i++)if(vis[i]==0){ dfs(i,basecmp++); }*/ for(int i=0;i<N;i++){vis[i]=0;graph[i].clear();} //} vector<query> Q; for(int i=L;i<R;i++){ for(query tmp:qrys[i]){ Q.push_back(tmp); } } sort(all(Q),comp_p); unordered_set<ll> swork[B]; for(int i=L;i<R;i++){ ll has=(ll)X[i]*Nmax+Y[i]; if(s.count(has))s.erase(has); else s.insert(has); swork[i-L]=s; } {//pの昇順に、左側の成分数を求める。base辺はyの昇順にソート uf::init(); ll benum=0; sort(all(baseedge),edge_comp_y); for(query qry:Q){ for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){ uf::unite(baseedge[benum].x,baseedge[benum].y); } vector<ll> conc; for(auto e:swork[qry.w-L]){ ll x=e/Nmax,y=e%Nmax; if(qry.p+1<=y)continue; x=uf::par(x),y=uf::par(y); graph[x].push_back(y); graph[y].push_back(x); conc.push_back(x); conc.push_back(y); } sort(all(conc)); conc.erase(unique(all(conc)),conc.end()); ll scmp=0; for(auto i:conc)if(vis[i]==0){ dfs(i,-1); scmp++; } for(auto i:conc){vis[i]=0;graph[i].clear();} fans[qry.id]+=(qry.p-uf::uni)-conc.size()+scmp; } } reverse(all(Q)); {//pの降順に、右側の成分数を求める。base辺はxの降順にソート uf::init(); ll benum=0; sort(all(baseedge),edge_comp_x); for(query qry:Q){ for(;benum<baseedge.size()&&baseedge[benum].x>=qry.p+1;benum++){ uf::unite(baseedge[benum].x,baseedge[benum].y); } vector<ll> conc; for(auto e:swork[qry.w-L]){ ll x=e/Nmax,y=e%Nmax; if(x<=qry.p)continue; x=uf::par(x),y=uf::par(y); graph[x].push_back(y); graph[y].push_back(x); conc.push_back(x); conc.push_back(y); } sort(all(conc)); conc.erase(unique(all(conc)),conc.end()); ll scmp=0; for(auto i:conc)if(vis[i]==0){ dfs(i,-1); scmp++; } for(auto i:conc){vis[i]=0;graph[i].clear();} fans[qry.id]+=(N-qry.p-uf::uni)-conc.size()+scmp; } } } return fans; }

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

collapse.cpp:19:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("O3")
 
collapse.cpp:20:0: warning: ignoring #pragma gcc optimize [-Wunknown-pragmas]
 #pragma gcc optimize("unroll-loops")
 
collapse.cpp:21:0: warning: ignoring #pragma gcc target [-Wunknown-pragmas]
 #pragma gcc target("avx2,see4")
 
collapse.cpp: In function 'vi simulateCollapse(int, vi, vi, vi, vi, vi)':
collapse.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<T.size();i++){
              ~^~~~~~~~~
collapse.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<W.size();i++){
              ~^~~~~~~~~
collapse.cpp:90:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int L=0;L<T.size();L+=B){
              ~^~~~~~~~~
collapse.cpp:146:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].y<=qry.p;benum++){
          ~~~~~^~~~~~~~~~~~~~~~
collapse.cpp:176:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;benum<baseedge.size()&&baseedge[benum].x>=qry.p+1;benum++){
          ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...