| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581093 |
2022-06-22T09:08:00 Z |
반딧불(#8360) |
Toll (APIO13_toll) |
C++17 |
|
176 ms |
804 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct unionFind{
int par[1002];
void init(int _n){
for(int i=0; i<=_n; i++) par[i]=i;
}
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[x] = y;
}
} dsu, dsu2;
struct Edge{
int x, y; ll z;
Edge(){}
Edge(int x, int y, ll z): x(x), y(y), z(z){}
bool operator<(const Edge &r)const{
return z<r.z;
}
};
int n, m, k;
vector<pair<int, ll> > link[1002];
bool isNew[1002][1002];
Edge edge[5002];
int ex[22], ey[22];
ll arr[1002];
ll ans;
vector<pair<int, ll> > rLink[1002];
vector<pair<int, int> > nLink[1002];
ll calc(int x, int p=-1, ll sum=0){
ll ret = arr[x] * sum;
for(auto y: rLink[x]){
if(y.first == p) continue;
ret += calc(y.first, x, sum + (isNew[x][y.first] ? y.second : 0));
}
return ret;
}
bool dfs(int x, int p, int goal, vector<int> &vec){
if(x==goal) return true;
for(auto y: nLink[x]){
if(y.first == p) continue;
vec.push_back(y.second);
if(dfs(y.first, x, goal, vec)) return true;
vec.pop_back();
}
for(auto y: rLink[x]){
if(y.first == p) continue;
if(dfs(y.first, x, goal, vec)) return true;
}
return false;
}
int main(){
scanf("%d %d %d", &n, &m, &k);
for(int i=1; i<=m; i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
edge[i] = Edge(x, y, z);
link[x].push_back(make_pair(y, z));
link[y].push_back(make_pair(x, z));
}
sort(edge+1, edge+m+1);
for(int i=0; i<k; i++){
scanf("%d %d", &ex[i], &ey[i]);
isNew[ex[i]][ey[i]] = 1;
isNew[ey[i]][ex[i]] = 1;
}
for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
for(int b=1; b<(1<<k); b++){ /// b: ���õ� �߰� �������� ����
/// cycle detection
dsu2.init(n);
bool bad = 0;
for(int i=1; i<=n; i++) nLink[i].clear();
for(int i=0; i<k; i++){
if((b&(1<<i))==0) continue;
if(dsu2.find(ex[i]) == dsu2.find(ey[i])){
bad = 1;
break;
}
dsu2.merge(ex[i], ey[i]);
nLink[ex[i]].push_back(make_pair(ey[i], i));
nLink[ey[i]].push_back(make_pair(ex[i], i));
}
if(bad) continue;
dsu.init(n);
for(int i=1; i<=n; i++) rLink[i].clear();
for(Edge e: edge){ /// ���� ����ġ ���� edge���� �õ��� ����
if(dsu.find(e.x) == dsu.find(e.y)) continue;
ll w = e.z;
if(dsu2.find(e.x) != dsu2.find(e.y)){ /// �߰��ص� �Ǵ� ���
rLink[e.x].push_back(make_pair(e.y, w));
rLink[e.y].push_back(make_pair(e.x, w));
dsu.merge(e.x, e.y);
dsu2.merge(e.x, e.y);
}
else{ /// �߰��ϸ� �ȵǴ� ���
vector<int> delVec;
dfs(e.x, -1, e.y, delVec);
for(auto x: delVec){
nLink[ex[x]].erase(find(nLink[ex[x]].begin(), nLink[ex[x]].end(), make_pair(ey[x], x)));
nLink[ey[x]].erase(find(nLink[ey[x]].begin(), nLink[ey[x]].end(), make_pair(ex[x], x)));
rLink[ex[x]].push_back(make_pair(ey[x], w));
rLink[ey[x]].push_back(make_pair(ex[x], w));
dsu.merge(ex[x], ey[x]);
}
}
}
ans = max(ans, calc(1));
}
printf("%lld", ans);
}
Compilation message
toll.cpp: In function 'int main()':
toll.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | scanf("%d %d %d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
74 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | scanf("%d %d", &ex[i], &ey[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:85:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | for(int i=1; i<=n; i++) scanf("%lld", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
18 ms |
340 KB |
Output is correct |
| 4 |
Correct |
17 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
18 ms |
340 KB |
Output is correct |
| 4 |
Correct |
17 ms |
340 KB |
Output is correct |
| 5 |
Correct |
176 ms |
804 KB |
Output is correct |
| 6 |
Correct |
80 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
18 ms |
340 KB |
Output is correct |
| 4 |
Correct |
17 ms |
340 KB |
Output is correct |
| 5 |
Correct |
176 ms |
804 KB |
Output is correct |
| 6 |
Correct |
80 ms |
724 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
18 ms |
340 KB |
Output is correct |
| 4 |
Correct |
17 ms |
340 KB |
Output is correct |
| 5 |
Correct |
176 ms |
804 KB |
Output is correct |
| 6 |
Correct |
80 ms |
724 KB |
Output is correct |
| 7 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 11 |
| 8 |
Halted |
0 ms |
0 KB |
- |
