이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |