제출 #782323

#제출 시각아이디문제언어결과실행 시간메모리
782323antonConstruction of Highway (JOI18_construction)C++17
16 / 100
2073 ms59816 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int, int> vector<int> colors; vector<int> time_g; vector<int> depth; map<int, int> m; struct Node{ int t; int last_m; int color; mutable vector<pii> cols; bool operator<( const Node& b)const{ return t<b.t; } Node(int id){ t = time_g[id]; color = colors[id]; last_m =id; //cols.push_back(pii(depth[id]-1, color)); } }; vector<vector<pii>> adj; void merge_pure(set<Node>&s, set<Node>&b, int prov){ for(auto e: b){ auto e2 = e; e2.last_m = prov; s.insert(e); } } void compute_rel(set<Node>::iterator a, set<Node>::iterator b, int d){ //cout<<a->t<<" "<<b->t<<endl; if(a->last_m!=b->last_m){ //cout<<m[a->t]+1<<" includes "<<m[b->t]+1<<endl; a->cols.push_back(pii(d, b->color)); } } void merge(set<Node>&a, set<Node>& b, int id){ for(auto it = b.begin(); it!=b.end(); it++){ auto pre = a.lower_bound((*it)); if(pre!=a.end()){ it++; if(it== b.end() || pre->t<it->t){ it--; compute_rel(pre, it, depth[id]); it++; } it--; } if(pre!=a.begin()){ pre--; if(pre!=a.end() && ((*pre)<(*it))){ //cout<<"pre "<<pre->t<<" "<<it->t<<endl; //cout<<((*pre)<(*it))<<endl; compute_rel(it, pre, depth[id]); } } a.insert(*it); } } set<Node> dfs(int id){ set<Node> res; set<Node> comp; if(adj[id].size()>0){ vector<set<Node>> sub; pii best = pii(0, 0); for(auto ch: adj[id]){ sub.push_back(dfs(ch.first)); if(sub.back().size()>best.first){ best.first = sub.back().size(); best.second = sub.size()-1; } } swap(res, sub[best.second]); for(int i = 0; i<sub.size(); i++){ if(i != best.second){ merge_pure(comp, sub[i],adj[id][i].first); } } } comp.insert(Node(id)); merge(res, comp, id); //cout<<id<<endl; for(auto e: res){ //cout<<m[e.t]+1<<" | "; } //cout<<endl<<endl<<endl; return res; } int merge(vector<pii>&v, int lt, int rt, int mid){ //cout<<"merging "<<lt<<" "<<rt<<" "<<mid<<endl; vector<pii> res; int c= 0; int l = lt; int r= mid+1; int r_s =0; for(int i = lt; i<=rt; i++){ if(l>mid){ res.push_back(v[r]); r_s += v[r].first; r++; } else if(r>rt){ res.push_back(v[l]); c+=(r_s)*v[l].first; l++; } else if(v[l].second<=v[r].second){ res.push_back(v[l]); c+=(r_s)*v[l].first; l++; } else{ res.push_back(v[r]); r_s += v[r].first; r++; } } for(int i = lt; i<=rt; i++){ v[i] = res[i-lt]; } return c; } int dpr(vector<pii>&v, int lt, int rt){ if(lt==rt){ return 0; } else{ //cout<<lt<<" "<<rt<<endl; int mid = (lt+rt)/2; int r =0; r+=dpr(v, lt, mid); r+=dpr(v, mid+1, rt); r+= merge(v, lt, rt, mid); //cout<<r<<endl; return r; } } signed main(){ int n; cin>>n; colors.resize(n); adj.resize(n); time_g.resize(n, -1); depth.resize(n, 1); for(int i = 0; i<n; i++){ int c; cin>>c; colors[i] = c; } m.insert(pii(-1, 0)); for(int i = 0; i<n-1; i++){ int a, b; cin>>a>>b; a--;b--; time_g[b] = i; adj[a].push_back(pii(b, i)); depth[b] = depth[a]+1; m.insert(pii(i, b)); } set<Node> res = dfs(0); //cout<<res.size()<<endl; for(auto e: res){ //cout<<"t: "<<m[e.t]+1<<" , "; for(auto c: e.cols){ //cout<<m[c.first]+1<<" "<<c.second<<" | "; } //cout<<endl; } vector<int> ans(n-1); for(auto e: res){ int cur= e.t; if(cur!=-1){ int r= 0; sort(e.cols.begin(), e.cols.end()); for(int i = e.cols.size()-1; i>0; i--){ e.cols[i].first -=e.cols[i-1].first; } for(auto ee:e.cols){ //cout<<ee.first<<" "<<ee.second<<" | "; } //cout<<endl; r += dpr(e.cols, 0, e.cols.size()-1); ans[cur]= r; } } //cout<<"_"<<endl; for(int i= 0; i<n-1; i++){ cout<<ans[i]<<endl; } }

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

construction.cpp: In function 'std::set<Node> dfs(long long int)':
construction.cpp:81:33: warning: comparison of integer expressions of different signedness: 'std::set<Node>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   81 |             if(sub.back().size()>best.first){
      |                ~~~~~~~~~~~~~~~~~^~~~~~~~~~~
construction.cpp:87:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::set<Node> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i = 0; i<sub.size(); i++){
      |                        ~^~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:194:18: warning: variable 'c' set but not used [-Wunused-but-set-variable]
  194 |         for(auto c: e.cols){
      |                  ^
construction.cpp:214:22: warning: variable 'ee' set but not used [-Wunused-but-set-variable]
  214 |             for(auto ee:e.cols){
      |                      ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...