Submission #1020765

#TimeUsernameProblemLanguageResultExecution timeMemory
1020765UnforgettableplReconstruction Project (JOI22_reconstruction)C++17
7 / 100
5092 ms6876 KiB
#pragma GCC optimize("Ofast","unroll-loops") #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e15; struct UFDS{ vector<int> p,siz; UFDS(int n):p(n+1),siz(n+1,1){iota(p.begin(),p.end(),0);} int findRoot(int x){ return p[x]==x ? x : p[x]=findRoot(p[x]); } bool unite(int a,int b){ a = findRoot(a); b = findRoot(b); if(a==b)return false; if(siz[a]<siz[b])swap(a,b); siz[a]+=siz[b]; p[b]=a; return true; } }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n,m; cin >> n >> m; vector<pair<int,pair<int,int>>> edges(m); for(auto&[a,b]:edges)cin>>b.first>>b.second>>a; // sort(edges.begin(),edges.end()); // vector<set<pair<int,int>>> adj; // vector<int> replaces_front(m,-1); // { // // Calculation from the front // adj = vector<set<pair<int,int>>>(n+1); // int tar; // function<pair<bool,int>(int,int)> dfs = [&](int x,int p){ // if(x==tar)return make_pair(true,(int)1e15); // for(auto[v,i]:adj[x])if(v!=p){ // auto res = dfs(v,x); // if(res.first)return make_pair(true,min(res.second,i)); // } // return make_pair(false,(int)0); // }; // for(int i=0;i<m;i++){ // tar = edges[i].second.second; // auto res = dfs(edges[i].second.first,-1); // if(res.first){ // adj[edges[res.second].second.first].erase({edges[res.second].second.second,res.second}); // adj[edges[res.second].second.second].erase({edges[res.second].second.first,res.second}); // replaces_front[i] = res.second; // } // adj[edges[i].second.first].insert({edges[i].second.second,i}); // adj[edges[i].second.second].insert({edges[i].second.first,i}); // } // } // vector<int> replaces_back(m,-1); // { // // Calculation from the back // adj = vector<set<pair<int,int>>>(n+1); // int tar; // function<pair<bool,int>(int,int)> dfs = [&](int x,int p){ // if(x==tar)return make_pair(true,(int)-1); // for(auto[v,i]:adj[x])if(v!=p){ // auto res = dfs(v,x); // if(res.first)return make_pair(true,max(res.second,i)); // } // return make_pair(false,(int)0); // }; // for(int i=m-1;i>=0;i--){ // tar = edges[i].second.second; // auto res = dfs(edges[i].second.first,-1); // if(res.first){ // adj[edges[res.second].second.first].erase({edges[res.second].second.second,res.second}); // adj[edges[res.second].second.second].erase({edges[res.second].second.first,res.second}); // replaces_back[i] = res.second; // } // adj[edges[i].second.first].insert({edges[i].second.second,i}); // adj[edges[i].second.second].insert({edges[i].second.first,i}); // } // } // set<int> curr_left; // set<int> curr_right; // for(auto&i:adj)for(auto[a,b]:i)curr_right.insert(b); auto solve = [&](int x){ vector<pair<int,int>> curredges; for(int i=0;i<m;i++){ curredges.emplace_back(abs(edges[i].first-x),i); } sort(curredges.begin(),curredges.end()); int ans = 0; UFDS dsu(n); for(auto[c,i]:curredges){ if(dsu.unite(edges[i].second.first,edges[i].second.second))ans+=c; } return ans; }; // int iter = 0; int q; cin >> q; for(int i=1;i<=q;i++){ int query; cin >> query; // while(iter!=m and edges[iter].first<query){ // curr_right.erase(iter); // if(replaces_back[iter]!=-1){ // curr_right.insert(replaces_back[iter]); // } // curr_left.insert(iter); // if(replaces_front[iter]!=-1){ // curr_left.erase(replaces_front[iter]); // } // iter++; // } cout << solve(query) << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...