| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581095 |
2022-06-22T09:11:58 Z |
반딧불(#8360) |
Toll (APIO13_toll) |
C++17 |
|
2500 ms |
32768 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct unionFind{
int par[100002];
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[100002];
unordered_set<ll> st;
Edge edge[500002];
int ex[22], ey[22];
ll arr[100002];
ll ans;
vector<pair<int, ll> > rLink[100002];
vector<pair<int, int> > nLink[100002];
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 + ((st.find(ll(x)*1000000+y.first) != st.end()) ? 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]);
st.insert(ll(ex[i])*1000000+ey[i]);
st.insert(ll(ey[i])*1000000+ex[i]);
}
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 |
7 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
1652 ms |
7360 KB |
Output is correct |
| 4 |
Correct |
1431 ms |
7380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
1652 ms |
7360 KB |
Output is correct |
| 4 |
Correct |
1431 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
2346 ms |
7744 KB |
Output is correct |
| 6 |
Correct |
1045 ms |
7740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
1652 ms |
7360 KB |
Output is correct |
| 4 |
Correct |
1431 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
2346 ms |
7744 KB |
Output is correct |
| 6 |
Correct |
1045 ms |
7740 KB |
Output is correct |
| 7 |
Execution timed out |
2586 ms |
32768 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
9 ms |
7372 KB |
Output is correct |
| 3 |
Correct |
1652 ms |
7360 KB |
Output is correct |
| 4 |
Correct |
1431 ms |
7380 KB |
Output is correct |
| 5 |
Correct |
2346 ms |
7744 KB |
Output is correct |
| 6 |
Correct |
1045 ms |
7740 KB |
Output is correct |
| 7 |
Execution timed out |
2586 ms |
32768 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
