oj.uz

Submission #918506

# Submission time Handle Problem Language Result Execution time Memory
918506 2024-01-30T02:12:40 Z Boycl07 Toll (APIO13_toll) C++17
100 / 100
 1385 ms 24152 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));
    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: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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct

Subtask #2
18.0 / 18.0

# 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 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10896 KB Output is correct

Subtask #3
22.0 / 22.0

# 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 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10896 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 4 ms 10840 KB Output is correct

Subtask #4
22.0 / 22.0

# 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 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10896 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 4 ms 10840 KB Output is correct
7 Correct 143 ms 23920 KB Output is correct
8 Correct 125 ms 23888 KB Output is correct
9 Correct 135 ms 24152 KB Output is correct

Subtask #5
22.0 / 22.0

# 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 Correct 3 ms 10844 KB Output is correct
4 Correct 3 ms 10896 KB Output is correct
5 Correct 5 ms 10844 KB Output is correct
6 Correct 4 ms 10840 KB Output is correct
7 Correct 143 ms 23920 KB Output is correct
8 Correct 125 ms 23888 KB Output is correct
9 Correct 135 ms 24152 KB Output is correct
10 Correct 992 ms 23912 KB Output is correct
11 Correct 1347 ms 23920 KB Output is correct
12 Correct 1385 ms 24060 KB Output is correct