Submission #86956

#	Time	Username	Problem	Language	Result	Execution time	Memory
86956		Alexa2001	Toll (APIO13_toll)	C++17	16 / 100	18 ms	14580 KiB

toll

#include <bits/stdc++.h>

using namespace std;

/// 18:01

typedef long long ll;
const int Nmax = 3e5 + 25;

int N, M, K, comps;


struct Edge
{
    int x, y, c;
    bool operator < (const Edge &other) const
    {
        return c < other.c;
    }
};
Edge edge[Nmax];


ll all_people[Nmax], sum[Nmax], people_sum[Nmax];
bool used_edge[Nmax];
int code[Nmax], where[Nmax], people[Nmax];

vector<Edge> E;
vector<int> c[Nmax], v[Nmax];


struct forest
{
    int T[Nmax];

    /*int boss(int x)
    {
        if(x == T[x]) return x;
        int y = x, z;

        while(x != T[x]) x = T[x];
        while(y != x) z = T[y], T[y] = x, y = z;

        return x;
    }*/

    int boss(int x)
    {
        if(x == T[x]) return x;
        return T[x] = boss(T[x]);
    }

    void init(int n)
    {
        int i;
        for(i=0; i<=n; ++i) T[i] = i;
    }

    bool unite(int x, int y)
    {
        x = boss(x); y = boss(y);
        if(x == y) return 0;
        T[x] = y;
        return 1;
    }
};
forest F;

void delete_redundant()
{
    forest F;
    F.init(N);

    int i;
    for(i=1; i<=K; ++i) F.unite(edge[i].x, edge[i].y);

    for(; i<=K+M; ++i)
        if(F.unite(edge[i].x, edge[i].y))
            used_edge[i] = 1;

    F.init(N);

    for(i=K+1; i<=K+M; ++i)
        if(used_edge[i])
            F.unite(edge[i].x, edge[i].y);

    comps = 0;
    for(i=1; i<=N; ++i)
    {
        if(!code[F.boss(i)]) code[F.boss(i)] = ++comps;
        where[i] = code[F.boss(i)];
    }

    for(i=1; i<=N; ++i)
        all_people[where[i]] += people[i];

    for(i=1; i<=K+M; ++i)
    {
        edge[i].x = where[edge[i].x];
        edge[i].y = where[edge[i].y];
    }

    for(i=K+1; i<=K+M; ++i)
        if(edge[i].x != edge[i].y)
            E.push_back(edge[i]);
}

void dfs3(int node, int dad = 0)
{
    int i;
    sum[node] = 0;
    people_sum[node] = all_people[node];

    for(i=0; i<v[node].size(); ++i)
    {
        int son = v[node][i], cost = c[node][i];
        if(son == dad) continue;

        dfs3(son, node);
        sum[node] += sum[son] + cost * people_sum[son];
        people_sum[node] += people_sum[son];
    }
}

ll solve(int mask)
{
    int i, j;
    F.init(comps);

//    for(i=1; i<=K; ++i)
  //      if(mask & (1<<i) && !F.unite(edge[i].x, edge[i].y)) return -1;

    vector<int> relevant;
    vector<Edge> final_edges;

    for(i=1; i<=K; ++i)
        if(mask & (1<<i)) relevant.push_back(i);


    for(auto it : E)
    {
        int nx = F.boss(it.x), ny = F.boss(it.y);
        if(nx == ny) continue;
        if(nx > ny) swap(nx, ny);

        bool used_edge = 1;

        for(j=0; j<relevant.size(); ++j)
        {
            Edge Q = edge[relevant[j]];
            int X = F.boss(Q.x), Y = F.boss(Q.y);
            if(X > Y) swap(X, Y);

            if(X == nx && Y == ny)
            {
                edge[relevant[j]].c = it.c;
                swap(relevant[j], relevant.back());
                relevant.pop_back();
                used_edge = 0;
                break;
            }
        }

        it.c = 0;
        if(used_edge) final_edges.push_back(it);
        F.unite(it.x, it.y);
    }

    if(relevant.size()) return -1;
    for(i=1; i<=K; ++i)
        if(mask & (1<<i)) final_edges.push_back(edge[i]);

    for(i=1; i<=comps; ++i) v[i].clear(), c[i].clear();

    for(auto e : final_edges)
    {
        v[e.x].push_back(e.y);
        v[e.y].push_back(e.x);
        c[e.x].push_back(e.c);
        c[e.y].push_back(e.c);
    }

    dfs3(where[1]);
    return sum[where[1]];
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> N >> M >> K;

    int i;
    for(i=1; i<=M; ++i)
        cin >> edge[K+i].x >> edge[K+i].y >> edge[K+i].c;

    sort(edge+K+1, edge+K+M+1);

    for(i=1; i<=K; ++i)
        cin >> edge[i].x >> edge[i].y;

    for(i=1; i<=N; ++i) cin >> people[i];

    delete_redundant();

    ll ans = -1;
    for(i=0; i<(1<<K); ++i) ans = max(ans, solve(i<<1));
    cout << ans << '\n';

    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void dfs3(int, int)':
toll.cpp:114:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
toll.cpp: In function 'll solve(int)':
toll.cpp:148:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0; j<relevant.size(); ++j)
                  ~^~~~~~~~~~~~~~~~

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