제출 #637900

#제출 시각아이디문제언어결과실행 시간메모리
637900Cross_RatioReconstruction Project (JOI22_reconstruction)C++14
3 / 100
5083 ms22780 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; ll A[2005]; ll B[2005]; ll C[2005]; // C[i] <= x < C[i+1], ans = x * A[i] + B[i]; typedef pair<ll, ll> P; ll dis[505][505]; ll dis2[505][505]; struct UnionFind { vector<int> root; UnionFind(int n) { root.resize(n); fill(root.begin(),root.end(),-1); } int Find(int n) { if(root[n]<0) return n; int r = Find(root[n]); root[n] = r; return r; } void Merge(int x, int y) { x = Find(x), y = Find(y); if(x==y) return; if(root[x]>root[y]) swap(x, y); root[x] += root[y]; root[y] = x; } }; vector<array<ll, 4>> Tree[2005]; vector<set<array<ll, 4>>> adj; array<ll, 4> Edge[100005]; bool S[100005]; void dfs(int c, int p, int rt) { for(auto n2 : adj[c]) { if(n2[0]==p) continue; dis[rt][n2[0]] = dis[rt][c]; dis2[rt][n2[0]] = dis2[rt][c]; if(dis[rt][n2[0]] > n2[1]) { dis[rt][n2[0]] = n2[1]; dis2[rt][n2[0]] = n2[2]; } dfs(n2[0], c, rt); } } signed main() { cin.sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M; cin >> N >> M; adj.resize(N); int i, j; for(i=0;i<M;i++) { int a, b, c; cin >> a>>b>>c; Edge[i] = {c, a-1, b-1, i}; } sort(Edge, Edge+M); UnionFind UF(N); for(i=0;i<M;i++) { Edge[i][3] = i; if(UF.Find(Edge[i][1])==UF.Find(Edge[i][2])) continue; UF.Merge(Edge[i][1], Edge[i][2]); Tree[0].push_back(Edge[i]); S[i] = true; adj[Edge[i][1]].insert({Edge[i][2], Edge[i][0], i}); adj[Edge[i][2]].insert({Edge[i][1], Edge[i][0], i}); } int cnt = 0; ll time = 0; C[cnt] = 0; for(auto it : Tree[0]) { A[0]--; B[0] += it[0]; } while(true) { cnt++; int i, j; for(i=0;i<N;i++) { for(j=0;j<N;j++) dis[i][j] = INF; } for(i=0;i<N;i++) { dfs(i, -1, i); } ll id = -1, ti = INF, id2 = -1; for(i=0;i<M;i++) { if(!S[i]) { ll mi = dis[Edge[i][1]][Edge[i][2]]; if(mi < Edge[i][0] && time < Edge[i][0]) { ll t2 = (mi+Edge[i][0]+1)/2; if(time > t2) continue; if(t2 < ti) { ti = t2; id = i; id2 = dis2[Edge[i][1]][Edge[i][2]]; } } } } //cout << id << ' ' << ti << ' ' << id2 << '\n'; ll t3 = INF; for(auto it : Tree[cnt-1]) { if(it[0]>time) t3 = min(t3, it[0]); } if(t3 != INF && t3 < ti) { C[cnt] = t3; Tree[cnt] = Tree[cnt-1]; time = t3; for(auto it : Tree[cnt-1]) { if(it[0]<=time) { A[cnt]++; B[cnt] -= it[0]; } else { A[cnt]--; B[cnt] += it[0]; } } //cout << C[cnt] << " : " << A[cnt] << ' '<< B[cnt] << '\n'; time = t3; continue; } if(id==-1) { C[cnt] = INF; break; } C[cnt] = ti; S[id] = true; S[id2] = false; adj[Edge[id2][1]].erase({Edge[id2][2], Edge[id2][0], id2}); adj[Edge[id2][2]].erase({Edge[id2][1], Edge[id2][0], id2}); adj[Edge[id][1]].insert({Edge[id][2], Edge[id][0], id}); adj[Edge[id][2]].insert({Edge[id][1], Edge[id][0], id}); for(auto it : Tree[cnt-1]) { if(it[3]!=id2) Tree[cnt].push_back(it); } Tree[cnt].push_back(Edge[id]); time = ti; for(auto it : Tree[cnt]) { //cout << it[0] << ' ' << it[1] << ' ' << it[2] << ' ' << it[3] << '\n'; if(it[0]<=time) { A[cnt]++; B[cnt] -= it[0]; } else { A[cnt]--; B[cnt] += it[0]; } } //cout << C[cnt] << " : " << A[cnt] << ' '<< B[cnt] << '\n'; } for(i=0;i<=cnt;i++) { //cout << C[i] << " : " << A[i] <<' ' << B[i] << '\n'; } int Q; cin >> Q; int ct = 0; while(Q--) { ll x; cin >> x; while(x>=C[ct+1]) ct++; ll ans = 0; cout << x * A[ct] + B[ct] << '\n'; } }

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

reconstruction.cpp: In function 'int main()':
reconstruction.cpp:164:12: warning: unused variable 'ans' [-Wunused-variable]
  164 |         ll ans = 0;
      |            ^~~
reconstruction.cpp:54:12: warning: unused variable 'j' [-Wunused-variable]
   54 |     int i, j;
      |            ^
#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...