Submission #681972

#	Time	Username	Problem	Language	Result	Execution time	Memory
681972		Magikarp4000	Race (IOI11_race)	C++17	0 / 100	3 ms	4948 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n'
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define in(v,x) (v.find(x) != v.end())
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PDD pair<double, double>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+1, MAXK = 1e6+1;
int n,k;
int h[MAXN][2], l[MAXN];
vector<pair<int,int>> v[MAXN];
int res = INF;
int dp[MAXN];
bool r[MAXN];
vector<UM<int,int>> mp;
UM<int,vector<pair<int,int>>> w;

//APPLEAPPLEAPPLEAPPLEAPPLEAPPLEAPPLEAPPLE BRUH

void dfs(int s,int pa) {
    dp[s]++;
    FORX(u,w[s]) {
        if (u.F == pa || r[u.F]) continue;
        dfs(u.F,s);
        dp[s] += dp[u.F];
    }
}

int decomp(int s, int pa, int cur) {
    bool ok = 1;
    FORX(u,w[s]) {
        if (u.F == pa || r[u.F]) continue;
        if (dp[u.F]*2 > cur) {
            return decomp(u.F,s,cur);
        }
    }
    return s;
}

void dfs1(int s, int pa, int id, int len, int cnt) {
    if (!mp[id].count(len)) mp[id][len] = cnt;
    else mp[id][len] = min(mp[id][len], cnt);
    FORX(u,w[s]) {
        if (u.F == pa || r[u.F] || len+u.S > k) continue;
        dfs1(u.F,s,id,len+u.S,cnt+1);
    }
}

void dfs2(int s, int pa) {
    FORX(u,v[s]) {
        if (u.F == pa) continue;
        w[u.F].PB({s,u.S});
        w[s].PB({u.F,u.S});
        dfs2(u.F,s);
    }
}

void COUTSUS() {
    FORX(u,w) {
        cout << u.F << ": ";
        FORX(y,u.S) cout << y.F << ' ';
        cout << ln;
    }
}

void solve(int root) {
    FOR(i,0,n) dp[i] = 0;
    dfs(root,-1);
    int cent = decomp(root,-1,dp[root]);
    UM<int,vector<PII>> vw;
    FORX(u,w) vw[u.F] = u.S;
    int num = 0;
    mp.clear();
    //FORX(u,mp) FORX(y,u) cout << y.F << " LOL\n";
    //cout << cent << ln;
    //cout << w[cent].size() << ln;
    FORX(u,w[cent]) {
        UM<int,int> tmp;
        mp.PB(tmp);
        dfs1(u.F,cent,num,u.S,1);
        num++;
    }
    UM<int,int> sus;
    sus[0] = 0;
    FORX(u,mp[0]) {
        if (!sus.count(u.F)) sus[u.F] = u.S;
        else sus[u.F] = min(sus[u.F],u.S);
        if (u.F == k) res = min(res,sus[u.F]);
    }
    //cout << cent << ln;
    FOR(i,1,(int)mp.size()) {
        //FORX(u,sus) cout << u.F << ' ' << u.S << ln;
        //cout << ln;
        FORX(u,mp[i]) {
            
            if (sus.count(k-u.F)) {
                // cout << "BRUH " << k-u.F << ' ' << sus[k-u.F] << ln;
                res = min(res,sus[k-u.F]+u.S);
                // cout << res << ln;
            }
            if (!sus.count(u.F)) sus[u.F] = u.S;
            else sus[u.F] = min(sus[u.F], u.S);
        }
    }
    //COUTSUS();
    //cout << ln;
    //cout << cent << ln;
    FORX(u,vw[cent]) {
        w.clear();
        dfs2(u.F,cent);
        solve(u.F);
    }
}

int best_path(int n, int k, int h[][2], int l[]) {
    FOR(i,0,n-1) {
        v[h[i][0]].PB({h[i][1],l[i]});
    }
    FOR(i,0,n) {
        FORX(u,v[i]) {
            w[i].PB({u.F,u.S});
            w[u.F].PB({i,u.S});
        }
    }
    solve(0);
    return res == INF ? -1 : res;
}

Compilation message (stderr)

race.cpp: In function 'int decomp(int, int, int)':
race.cpp:48:10: warning: unused variable 'ok' [-Wunused-variable]
   48 |     bool ok = 1;
      |          ^~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57