Submission #1443993
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;
const int MAXN = 4005;
struct disj{
int pa[MAXN];
void init(int n){
iota(pa, pa + n + 1, 0);
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
struct edg{
int s, e, x;
bool operator<(const edg &e)const{
return x < e.x;
}
};
int n, m;
vector<pi> gph[MAXN];
vector<edg> ed;
int dep[MAXN], par[12][MAXN], pva[12][MAXN];
void dfs(int x, int p){
for(auto &i : gph[x]){
if(i.second == p) continue;
par[0][i.second] = x;
pva[0][i.second] = i.first;
dep[i.second] = dep[x] + 1;
dfs(i.second, x);
}
}
int get(int s, int e){
if(dep[e] < dep[s]) swap(s, e);
int dx = dep[e] - dep[s];
int ans = 0;
for(int i=0; i<12; i++){
if((dx >> i) & 1){
ans = max(ans, pva[i][e]);
e = par[i][e];
}
}
for(int i=11; i>=0; i--){
if(par[i][s] != par[i][e]){
ans = max({ans, pva[i][s], pva[i][e]});
s = par[i][s];
e = par[i][e];
}
}
if(s != e){
ans = max({ans, pva[0][s], pva[0][e]});
}
return ans;
}
int main(){
cin >> n >> m;
for(int i=0; i<m; i++){
int s, e, x;
scanf("%d %d %d",&s,&e,&x);
ed.push_back({s, e, x});
}
sort(ed.begin(), ed.end());
lint ans = 0;
disj.init(n);
for(auto &i : ed){
if(disj.uni(i.s, i.e)){
ans += i.x;
gph[i.s].push_back(pi(i.x, i.e));
gph[i.e].push_back(pi(i.x, i.s));
}
}
dfs(1, 0);
for(int i=1; i<12; i++){
for(int j=1; j<=n; j++){
par[i][j] = par[i-1][par[i-1][j]];
pva[i][j] = max(pva[i-1][j], pva[i-1][par[i-1][j]]);
}
}
int q;
scanf("%d",&q);
while(q--){
int s, e;
scanf("%d %d",&s,&e);
printf("%lld\n", ans - get(s, e));
}
}
Submission Info
Submission Time |
|
Task |
A - Graph |
User |
koosaga |
Language |
C++14 (GCC 5.4.1) |
Score |
700 |
Code Size |
1927 Byte |
Status |
AC |
Exec Time |
177 ms |
Memory |
8560 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:74:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&s,&e,&x);
^
./Main.cpp:95:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
^
./Main.cpp:98:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&s,&e);
^
Judge Result
Set Name |
Sample |
subtask1 |
subtask2 |
All |
Score / Max Score |
0 / 0 |
200 / 200 |
300 / 300 |
200 / 200 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt |
subtask1 |
sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt |
subtask2 |
sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt |
All |
sample_1.txt, sample_2.txt, sample_1.txt, sample_2.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt, subtask_2_1.txt, subtask_2_2.txt, subtask_2_3.txt, subtask_2_4.txt, subtask_2_5.txt, subtask_2_6.txt, subtask_2_7.txt, subtask_2_8.txt, subtask_3_1.txt, subtask_3_2.txt, subtask_3_3.txt, subtask_3_4.txt, subtask_3_5.txt, subtask_3_6.txt, subtask_3_7.txt, subtask_3_8.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_1.txt |
AC |
1 ms |
384 KB |
sample_2.txt |
AC |
1 ms |
384 KB |
subtask_1_1.txt |
AC |
2 ms |
512 KB |
subtask_1_10.txt |
AC |
67 ms |
3572 KB |
subtask_1_11.txt |
AC |
1 ms |
384 KB |
subtask_1_2.txt |
AC |
15 ms |
1400 KB |
subtask_1_3.txt |
AC |
133 ms |
7408 KB |
subtask_1_4.txt |
AC |
3 ms |
896 KB |
subtask_1_5.txt |
AC |
4 ms |
896 KB |
subtask_1_6.txt |
AC |
34 ms |
2040 KB |
subtask_1_7.txt |
AC |
132 ms |
8176 KB |
subtask_1_8.txt |
AC |
3 ms |
896 KB |
subtask_1_9.txt |
AC |
5 ms |
960 KB |
subtask_2_1.txt |
AC |
134 ms |
7024 KB |
subtask_2_2.txt |
AC |
133 ms |
8176 KB |
subtask_2_3.txt |
AC |
134 ms |
6896 KB |
subtask_2_4.txt |
AC |
134 ms |
6640 KB |
subtask_2_5.txt |
AC |
4 ms |
1024 KB |
subtask_2_6.txt |
AC |
10 ms |
1148 KB |
subtask_2_7.txt |
AC |
36 ms |
2040 KB |
subtask_2_8.txt |
AC |
133 ms |
8432 KB |
subtask_3_1.txt |
AC |
171 ms |
8432 KB |
subtask_3_2.txt |
AC |
177 ms |
7532 KB |
subtask_3_3.txt |
AC |
41 ms |
2304 KB |
subtask_3_4.txt |
AC |
45 ms |
2240 KB |
subtask_3_5.txt |
AC |
106 ms |
4336 KB |
subtask_3_6.txt |
AC |
140 ms |
7152 KB |
subtask_3_7.txt |
AC |
172 ms |
7792 KB |
subtask_3_8.txt |
AC |
171 ms |
8560 KB |