Submission #918506

#	Time	Username	Problem	Language	Result	Execution time	Memory
918506		Boycl07	Toll (APIO13_toll)	C++17	100 / 100	1385 ms	24152 KiB

toll

#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));
    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 (stderr)

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:204:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  204 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22