Submission #98938

#	Time	Username	Problem	Language	Result	Execution time	Memory
98938		Akashi	Toll (APIO13_toll)	C++14	0 / 100	10 ms	7808 KiB

toll

#include <bits/stdc++.h>
using namespace std;



struct edge{
    int x, y, k, ok;
    bool operator < (const edge &aux)const{
        if(k != aux.k) return k < aux.k;
        return ok > aux.ok;
    }
};

int tt[100005], RG[100005];
inline int Find(int x){
    int R = x;
    while(R != tt[R]) R = tt[R];
    while(x != tt[x]){
        int aux = tt[x];
        tt[x] = R; x = aux;
    }
    return R;
}
inline void Union(int x, int y){
    if(RG[x] > RG[y]) tt[y] = x;
    else if(RG[x] < RG[y]) tt[x] = y;
    else{
        ++RG[x];
        tt[y] = x;
    }
}


edge a[300005];
vector <pair <int, int> > v[100005];
vector <int> lant[100005];
int **Arb, **w;

int nrl, n, m, k;
int TT[100005], TT_lant[100005], wlant[100005], nrp[100005], val[100005], pos[100005], H[100005];

namespace aint{
    void build(int i, int st, int dr, int nod){
        if(st == dr){
            Arb[i][nod] = val[lant[i][st - 1]];
            w[i][nod] = st;
            return ;
        }

        int mij = (st + dr) / 2;
        build(i, st, mij, nod * 2);
        build(i, mij + 1, dr, nod * 2 + 1);

        if(Arb[i][nod * 2] >= Arb[i][nod * 2 + 1]){
            Arb[i][nod] = Arb[i][nod * 2];
            w[i][nod] = w[i][nod * 2];
        }
        else{
            Arb[i][nod] = Arb[i][nod * 2 + 1];
            w[i][nod] = w[i][nod * 2 + 1];
        }
    }

    void update(int i, int st, int dr, int nod, int x, int y){
        if(st == dr){
            Arb[i][nod] = y;
            return ;
        }

        int mij = (st + dr) / 2;
        if(x <= mij) update(i, st, mij, nod * 2, x, y);
        else update(i, mij + 1, dr, nod * 2 + 1, x, y);

        if(Arb[i][nod * 2] >= Arb[i][nod * 2 + 1]){
            Arb[i][nod] = Arb[i][nod * 2];
            w[i][nod] = w[i][nod * 2];
        }
        else{
            Arb[i][nod] = Arb[i][nod * 2 + 1];
            w[i][nod] = w[i][nod * 2 + 1];
        }
    }

    pair <int, int> query(int i, int st, int dr, int nod, int x, int y){
        if(x <= st && dr <= y) return {Arb[i][nod], w[i][nod]};

        int mij = (st + dr) / 2;
        pair <int, int> p1 = {0, 0};
        pair <int, int> p2 = {0, 0};

        if(x <= mij) p1 = query(i, st, mij, nod * 2, x, y);
        if(mij + 1 <= y) p2 = query(i, mij + 1, dr, nod * 2 + 1, x, y);

        if(p1.first >= p2.first) return p1;
        return p2;
    }
}

inline int dfs(int nod = 1){
    int w = 0, frunza = 1, sz = 0, max_sz = 0;
    for(auto it : v[nod]){
        if(it.first == TT[nod]) continue ;
        frunza = 0;

        H[it.first] = H[nod] + 1;
        val[it.first] = it.second;
        TT[it.first] = nod;
        int c_sz = dfs(it.first);
        sz += c_sz;

        if(c_sz > max_sz){
            w = it.first;
            max_sz = c_sz;
        }
    }

    if(frunza){
        lant[++nrl].push_back(nod);
        wlant[nod] = nrl;
        return 1;
    }

    int wl = wlant[w];
    wlant[nod] = wl;
    lant[wl].push_back(nod);

    for(auto it : v[nod]){
        if(it.first == TT[nod]) continue ;
        TT_lant[it.first] = wl;
    }

    return sz + 1;
}

pair <int, int> ans(int x, int y){
    pair <int, int> Sol = {0, 0};
    while(1){
        int lx = wlant[x], ly = wlant[y];

        if(lx == ly){
            int st = min(pos[x], pos[y]);
            int dr = max(pos[x], pos[y]);
            Sol = max(Sol, aint :: query(lx, 1, lant[lx].size(), 1, st, dr));
            break ;
        }

        if(H[lant[lx][0]] < H[lant[ly][0]]) swap(x, y), swap(lx, ly);

        Sol = max(Sol, aint :: query(lx, 1, lant[lx].size(), 1, 1, pos[x]));
        x = lant[lx][0];
        x = TT[x];
    }
    return Sol;
}

struct usu{
    int x, k, ok;
};
vector <usu> v2[100005];
vector <int> Sol;
vector <int> Sol2;


void dfs2(int nod = 1){
    int cnt = 0;
    for(auto it : v2[nod]){
        if(it.x == TT[nod]) continue ;
        TT[it.x] = nod;
        dfs2(it.x);
        if(it.ok) Sol.push_back(nrp[it.x]);
        nrp[nod] += nrp[it.x];
    }
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d%d", &n, &m, &k);

    for(int i = 1; i <= m ; ++i)
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k);

    for(int i = 1; i <= n ; ++i) tt[i] = i, RG[i] = 1;
    sort(a + 1, a + m + 1);
    for(int i = 1; i <= m ; ++i){
        if(Find(a[i].x) != Find(a[i].y)){
            Union(Find(a[i].x), Find(a[i].y));
            v[a[i].x].push_back({a[i].y, a[i].k});
            v[a[i].y].push_back({a[i].x, a[i].k});
        }
    }

    dfs();

    Arb = new int*[nrl + 1];
    w = new int*[nrl + 1];
    for(int i = 1; i <= nrl ; ++i){
        reverse(lant[i].begin(), lant[i].end());
        Arb[i] = new int[lant[i].size() * 4 + 5];
        w[i] = new int[lant[i].size() * 4 + 5];
        aint :: build(i, 1, lant[i].size(), 1);

        int NR = 0;
        for(auto it : lant[i])
            pos[it] = ++NR;
    }

    int x, y;
    vector <int> val;
    for(int i = 1; i <= k ; ++i){
        scanf("%d%d", &x, &y);
        pair <int, int> p = ans(x, y);
        val.push_back(p.first);
        if(p.second == 0) continue ;
        aint :: update(wlant[p.second], 1, lant[wlant[p.second]].size(), 1, pos[p.second], 0);
        a[++m] = {x, y, p.first, 1};
        Sol2.push_back(p.first);
    }

    for(int i = 1; i <= n ; ++i) tt[i] = i, RG[i] = 1;

    sort(a + 1, a + m + 1);
    for(int i = 1; i <= m ; ++i){
        if(Find(a[i].x) != Find(a[i].y)){
            Union(Find(a[i].x), Find(a[i].y));
            v2[a[i].x].push_back({a[i].y, a[i].k, a[i].ok});
            v2[a[i].y].push_back({a[i].x, a[i].k, a[i].ok});
        }
    }

    for(int i = 1; i <= n ; ++i)
        scanf("%d", &nrp[i]);

    memset(TT, 0, sizeof(TT));
    dfs2();


    long long mm = 0;
    sort(Sol.begin(), Sol.end());
    sort(Sol2.begin(), Sol2.end());
    for(int i = 0; i < Sol.size() ; ++i)
        mm = 1LL * Sol[i] * Sol2[i];

    printf("%lld", mm);
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void dfs2(int)':
toll.cpp:165:9: warning: unused variable 'cnt' [-Wunused-variable]
     int cnt = 0;
         ^~~
toll.cpp: In function 'int main()':
toll.cpp:242:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < Sol.size() ; ++i)
                    ~~^~~~~~~~~~~~
toll.cpp:179:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &n, &m, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:182:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].k);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:212:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
toll.cpp:233:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &nrp[i]);
         ~~~~~^~~~~~~~~~~~~~~

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