Submission #445591

#	Time	Username	Problem	Language	Result	Execution time	Memory
445591		JerryLiu06	Islands (IOI08_islands)	C++17	80 / 100	1264 ms	131076 KiB

islands

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
using db = double;
using str = string;
 
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
 
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
 
#define mp make_pair
#define f first
#define s second
 
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert 
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
 
#define lb lower_bound
#define ub upper_bound
 
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
 
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
 
const int MOD = 1e9 + 7;
const int MX = 1e6 + 10;
const ll INF = 1e18;

int N; vpi adj[MX]; pi nxt[MX]; ll ans = 0;

vi vis; ll label[MX]; ll cycLen[MX];

int numCyc = 0; bool comp[MX]; vector<vi> cyc;

int numTree = 0; vector<vi> tree;

ll val[MX], dist[MX];

queue<int> Q;

ll DFS2(int X, int P, int curTree) {
    tree[curTree].pb(X);
    ll maxDist = 0;

    EACH(Y, adj[X]) {
        if (Y.f != P && !comp[Y.f]) {
            ckmax(maxDist, DFS2(Y.f, X, numTree) + Y.s);
        }
    }
    return maxDist;
}

pl furthestAway(int X, int ind) {
	while (!Q.empty()) Q.pop();
	
	EACH(i, tree[ind]) dist[i] = -1;

    Q.push(X); dist[X] = 0; pl res = {-1, -1};

    while (!Q.empty()) {
        int cur = Q.front(); Q.pop();
        
        ckmax(res, {dist[cur], cur});

        EACH(nxt, adj[cur]) {
            if (dist[nxt.f] == -1) {
                
                dist[nxt.f] = dist[cur] + nxt.s;
                Q.push(nxt.f);
            }
        }
    }
	return res;
}
ll getDiam(int ind) {
    int ST = furthestAway(tree[ind][0], ind).s;
    
    return furthestAway(ST, ind).f;
}

// DFS in Functional Graph ~ Generate cycles

void DFS1(int X) {
    int cur = X; 
    
    while (vis[X] == 0) { 
        vis[X] = cur; 
        X = nxt[X].f; 
    }

    ll curDist = 0; if (vis[X] == cur) numCyc++, cyc.pb(vi());
    
    while (vis[X] == cur) { 
        vis[X] = N + cur; 
        label[X] = curDist; 
        comp[X] = true;
        cyc[numCyc].pb(X);

        curDist += nxt[X].s;
        
        X = nxt[X].f;
    }
    if (vis[X] == N + cur) {
        cycLen[numCyc] = curDist;
    }
    while (vis[X] == N + cur) {
        vis[X] = 2 * N + cur;
        
        tree.pb(vi());
        val[X] = DFS2(X, 0, ++numTree);
        
        X = nxt[X].f;
    }
}

ll getMaxDist(int ind) {
    ll res = 0;
    
    EACH(X, cyc[ind]) {
        ckmax(res, getDiam(++numTree));
    }
    
    // case 1: i < j, val[j] + label[j] + val[i] - label[i]
    
    ll cumMax = -INF; 
    
    FOR(i, 1, sz(cyc[ind])) {
        int A = cyc[ind][i];
        
        int B = cyc[ind][i - 1];
        
        ckmax(cumMax, val[B] - label[B]);
        
        ckmax(res, val[A] + label[A] + cumMax);
    }
    
    // case 2: i < j, cyclen[ind] + val[j] - label[j] + val[i] + label[i]
    
    cumMax = -INF;
    
    FOR(i, 1, sz(cyc[ind])) {
        int A = cyc[ind][i];
        
        int B = cyc[ind][i - 1];
        
        ckmax(cumMax, val[B] + label[B]);
        
        ckmax(res, cycLen[ind] + val[A] - label[A] + cumMax);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N; 

    FOR(i, 1, N + 1) { 
        int A, L; cin >> A >> L; 
        adj[i].pb({A, L}), adj[A].pb({i, L}); 
        nxt[i] = {A, L}; 
    }
    vis.rsz(N + 1);
    tree.pb(vi()); cyc.pb(vi());

    FOR(i, 1, N + 1) {
        if (!vis[i]) {
            DFS1(i);
        }
    }
    vis.clear();
    // FOR(i, 1, numTree + 1) {
    //     getDiam(i);
    // }
    numTree = 0;
    FOR(i, 1, numCyc + 1) {
        ans += getMaxDist(i);
    }
    cout << ans;
}

Compilation message (stderr)

islands.cpp: In function 'll getMaxDist(int)':
islands.cpp:149:10: warning: unused variable 'X' [-Wunused-variable]
  149 |     EACH(X, cyc[ind]) {
      |          ^
islands.cpp:45:31: note: in definition of macro 'EACH'
   45 | #define EACH(a, x) for (auto& a : x)
      |                               ^

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10