| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 918505 |
2024-01-30T02:12:19 Z |
Boycl07 |
Toll (APIO13_toll) |
C++17 |
|
2 ms |
10844 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "toll"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
inline int readInt() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong() {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 1e5 + 4;
const int M = 3e5 + 3;
const int K = 22;
const int INF = 1e9 + 3;
const ll LINF = 1e18;
int n, m, k;
struct edge
{
int u, v, w;
bool operator < (const edge &x) {
return w < x.w;
}
};
edge edges[M + K];
bool in_mst[M + K], flag[M + K];
struct Dsu
{
int par[N], sz[N];
void init(int sz_)
{
rep(i, sz_) par[i] = i, sz[i] = 1;
}
int find_set(int u) {return u == par[u] ? u : par[u] = find_set(par[u]);}
bool union_set(int u, int v)
{
if((u = find_set(u)) == (v = find_set(v))) return 0;
if(sz[u] < sz[v]) swap(u, v);
par[v] = u;
sz[u] += sz[v];
return 1;
}
} dsu;
vector<int> extra;
int num = 0;
int cnt[N], sum[N], pass[N];
int idx[N], par[N], depth[N], mi[N];
vector<pii> adj[N];
void dfs_pre(int u, int p)
{
depth[u] = depth[p] + 1;
par[u] = p;
sum[u] = cnt[u];
for(pii e : adj[u])
{
int v = e.fi;
int idx = e.se;
if(v == p) continue;
dfs_pre(v, u);
sum[u] += sum[v];
}
}
void update(int u, int v, int w)
{
while(u != v)
{
if(depth[u] < depth[v]) swap(u, v);
minimize(mi[u], w);
u = par[u];
}
}
ll cur = 0;
void dfs_solve(int u, int p)
{
for(pii e : adj[u])
{
int v = e.fi;
int idx = e.se;
if(v == p) continue;
dfs_solve(v, u);
if(idx > m) cur += 1ll * sum[v] * mi[v];
}
}
ll get(int mask)
{
cur = 0;
dsu.init(num);
rep(i, num) adj[i].clear(), mi[i] = INF;
vector<int> f;
forn(i, 1, k) if(mask >> i - 1 & 1)
{
int u = idx[edges[i + m].u];
int v = idx[edges[i + m].v];
if(dsu.union_set(u, v)) adj[u].pb({v, i + m}), adj[v].pb({u, i + m});
else return -1;
}
for(int x : extra)
{
int u = idx[edges[x].u];
int v = idx[edges[x].v];
if(dsu.union_set(u, v)) adj[u].pb({v, x}), adj[v].pb({u, x});
else f.pb(x);
}
depth[idx[1]] = 0;
dfs_pre(idx[1], idx[1]);
for(int x : f)
{
update(idx[edges[x].u], idx[edges[x].v], edges[x].w);
}
dfs_solve(idx[1], idx[1]);
return cur;
}
void solve()
{
cin >> n >> m >> k;
rep(i, m) cin >> edges[i].u >> edges[i].v >> edges[i].w;
forn(i, m + 1, m + k) cin >> edges[i].u >> edges[i].v;
rep(i, n) cin >> pass[i];
dsu.init(n);
sort(edges + 1, edges + 1 + m);
rep(i, m) flag[i] = dsu.union_set(edges[i].u, edges[i].v);
dsu.init(n);
ford(i, m + k, m + 1) in_mst[i] = dsu.union_set(edges[i].u, edges[i].v);
forn(i, 1, m)
{
in_mst[i] = dsu.union_set(edges[i].u, edges[i].v);
}
dsu.init(n);
rep(i, m)
if(in_mst[i]) dsu.union_set(edges[i].u, edges[i].v);
else if(flag[i]) extra.pb(i);
rep(i, n) if(i == dsu.find_set(i)) idx[i] = ++num;
rep(i, n) idx[i] = idx[dsu.find_set(i)];
rep(i, n) cnt[idx[i]] += pass[i];
ll res = 0;
//forn(mask, 0, (1 << k) - 1) maximize(res, get(mask));
res = get(7);
cout << res;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int TC = 1;
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
while(TC--)
{
solve();
cout << endl;
}
return 0;
}
Compilation message
toll.cpp: In function 'void dfs_pre(ll, ll)':
toll.cpp:85:13: warning: unused variable 'idx' [-Wunused-variable]
85 | int idx = e.se;
| ^~~
toll.cpp: In function 'll get(ll)':
toll.cpp:123:32: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
123 | forn(i, 1, k) if(mask >> i - 1 & 1)
| ~~^~~
toll.cpp: In function 'int main()':
toll.cpp:205:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
205 | freopen(task".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:206:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
206 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10844 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
10840 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
