Submission #1005666
Source Code Expand
#include <iostream> #include <vector> #include <string> #include <cmath> #include <algorithm> using namespace std; int root[4001]; int del[4001][4001]={}; int p; vector<pair<int,int> > graph[4001]; int find(int x){ if(x != root[x]){ root[x]=find(root[x]); } return root[x]; } void union_set(int x,int y){ x=find(x); y=find(y); if(x!=y){ root[x]=y; } return; } void dfs(int x,int y,int z){ del[p][x] = z; for(int i=0;i<graph[x].size();i++){ if(graph[x][i].first==y)continue; dfs(graph[x][i].first,x,max(z,graph[x][i].second)); } } int main(){ for(int i=0;i<4001;i++){ root[i] = i; } int n,m,q,a,b,s,t,c; long long ans=0; long long sum=0; vector<pair<long long,pair<int,int> > > node,node2; cin >> n >> m; for(int i=0;i<m;i++){ pair<long long,pair<int,int> > tmp; cin >> a >> b >> c; tmp = make_pair(c,make_pair(a,b)); node.push_back(tmp); } sort(node.begin(),node.end()); for(int i=0;i<node.size();i++){ if(find(node[i].second.first)!=find(node[i].second.second)){ sum += node[i].first; union_set(node[i].second.first,node[i].second.second); node2.push_back(node[i]); graph[node[i].second.first].push_back(make_pair(node[i].second.second,node[i].first)); graph[node[i].second.second].push_back(make_pair(node[i].second.first,node[i].first)); } } for(p=1;p<=n;p++){ dfs(p,-1,-1); } cin >> q; for(int i=0;i<q;i++){ cin >> s >> t; ans = sum-del[s][t]; cout << ans << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Graph |
User | mtsd |
Language | C++14 (GCC 5.4.1) |
Score | 700 |
Code Size | 1532 Byte |
Status | AC |
Exec Time | 1284 ms |
Memory | 70504 KB |
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, 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 | 3 ms | 384 KB |
sample_2.txt | AC | 3 ms | 384 KB |
subtask_1_1.txt | AC | 4 ms | 768 KB |
subtask_1_10.txt | AC | 599 ms | 66284 KB |
subtask_1_11.txt | AC | 3 ms | 384 KB |
subtask_1_2.txt | AC | 450 ms | 63732 KB |
subtask_1_3.txt | AC | 796 ms | 69352 KB |
subtask_1_4.txt | AC | 386 ms | 63232 KB |
subtask_1_5.txt | AC | 406 ms | 63104 KB |
subtask_1_6.txt | AC | 498 ms | 64624 KB |
subtask_1_7.txt | AC | 792 ms | 69352 KB |
subtask_1_8.txt | AC | 378 ms | 63104 KB |
subtask_1_9.txt | AC | 411 ms | 63228 KB |
subtask_2_1.txt | AC | 813 ms | 69352 KB |
subtask_2_2.txt | AC | 805 ms | 69352 KB |
subtask_2_3.txt | AC | 808 ms | 69352 KB |
subtask_2_4.txt | AC | 817 ms | 69352 KB |
subtask_2_5.txt | AC | 397 ms | 63232 KB |
subtask_2_6.txt | AC | 441 ms | 63480 KB |
subtask_2_7.txt | AC | 514 ms | 64624 KB |
subtask_2_8.txt | AC | 806 ms | 69352 KB |
subtask_3_1.txt | AC | 1278 ms | 70504 KB |
subtask_3_2.txt | AC | 1283 ms | 70504 KB |
subtask_3_3.txt | AC | 864 ms | 64512 KB |
subtask_3_4.txt | AC | 901 ms | 64508 KB |
subtask_3_5.txt | AC | 1098 ms | 67436 KB |
subtask_3_6.txt | AC | 1186 ms | 68968 KB |
subtask_3_7.txt | AC | 1284 ms | 70504 KB |
subtask_3_8.txt | AC | 1283 ms | 70504 KB |