Submission #725228

#	Time	Username	Problem	Language	Result	Execution time	Memory
725228		n0sk1ll	Swapping Cities (APIO20_swap)	C++14	7 / 100	445 ms	40032 KiB

swap

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

#include "swap.h"

namespace dsu
{
    int up[100005];

    void build(int n)
    {
        ff(i,0,n) up[i]=-1;
    }

    int Up(int x)
    {
        if (up[x]<0) return x;
        return up[x]=Up(up[x]);
    }

    void dsu(int a, int b)
    {
        a=Up(a),b=Up(b);
        if (a==b) return;
        if (up[a]<up[b]) swap(a,b);
        up[b]+=up[a],up[a]=b;
    }
}

//kad nadjemo spanning tree:
vector<vector<pii>> g(100005);
int tin[100005],tout[100005];
int up[17][100005],we[17][100005],twe[17][100005];
int dp[100005]; //min twe u subtree
int VREME=0;

void dfs(int p, int q, int qw)
{
    tin[p]=++VREME,up[0][p]=q,we[0][p]=qw;
    for (auto [it,w] : g[p]) if (it!=q) dfs(it,p,w);
    tout[p]=VREME;
}

void tfs(int p, int q)
{
    dp[p]=twe[0][p];
    for (auto [it,w] : g[p]) if (it!=q)
    {
        tfs(it,p);
        dp[p]=min(dp[p],max(w,dp[it]));
    }
}

void build(int n)
{
    ff(i,0,n)
    {
        vector<int> temp;
        for (auto [it,w] : g[i]) temp.pb(w);
        if ((int)temp.size()<3) twe[0][i]=mod;
        else sort(all(temp)),twe[0][i]=temp[2];
    }

    tfs(0,0);

    ff(k,1,17) ff(i,0,n)
    {
        up[k][i]=up[k-1][up[k-1][i]];
        we[k][i]=max(we[k-1][i],we[k-1][up[k-1][i]]);
        twe[k][i]=min(twe[k-1][i],twe[k-1][up[k-1][i]]);
    }
}

bool anc(int a, int b)
{
    return tin[a]<=tin[b] && tout[a]>=tout[b];
}

int Lca(int a, int b, int &maxput, int &mintwe)
{
    bff(k,0,17) if (!anc(up[k][a],b))
    {
        mintwe=min(mintwe,twe[k][a]);
        maxput=max(maxput,we[k][a]);
        a=up[k][a];
    }
    bff(k,0,17) if (!anc(up[k][b],a))
    {
        mintwe=min(mintwe,twe[k][b]);
        maxput=max(maxput,we[k][b]);
        b=up[k][b];
    }

    if (anc(b,a)) swap(a,b);
    if (anc(a,b))
    {
        mintwe=min(mintwe,twe[0][b]);
        maxput=max(maxput,we[0][b]);
        mintwe=min(mintwe,twe[0][a]);
        return a;
    }

    mintwe=min(mintwe,twe[0][b]);
    mintwe=min(mintwe,twe[0][a]);
    maxput=max(maxput,we[0][a]);
    maxput=max(maxput,we[0][b]);

    a=up[0][a];
    mintwe=min(mintwe,twe[0][a]);
    return a;
}

void init(int n, int m, vector<int> u, vector<int> v, vector<int> w)
{
    vector<pair<int,pii>> sorta;
    ff(i,0,m) sorta.pb({w[i],{u[i],v[i]}});
    sort(all(sorta));

    vector<pair<int,pii>> izdajnici;

    dsu::build(n);
    for (auto it : sorta)
    {
        int a=it.yy.xx,b=it.yy.yy;
        int pa=dsu::Up(a),pb=dsu::Up(b);
        if (pa!=pb) g[a].pb({b,it.xx}),g[b].pb({a,it.xx}),dsu::dsu(pa,pb);
        else izdajnici.pb(it);
    }

    dfs(0,0,0);
    build(n);

    for (auto it : izdajnici)
    {
        int nebitno=-1;
        int a=it.yy.xx,b=it.yy.yy,w=it.xx;
        int c=Lca(a,b,nebitno,nebitno);
        //darksoul[c]=min(darksoul[c],w);
    }
}

int getMinimumFuelCapacity(int a, int b)
{
    int maxput=0,spas=mod;
    int c=Lca(a,b,maxput,spas);
    spas=min(spas,dp[c]);
    if (spas==mod) return -1;
    return max(maxput,spas);
}

/*

5 4
0 1 1
1 2 1
2 3 1
3 4 1
10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4

5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2

11 10
0 1 5
1 2 4
2 3 3
2 4 10
1 5 1
5 6 2
5 7 2
0 8 10
8 9 1
8 10 1
10
1 0
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10


*/

Compilation message (stderr)

swap.cpp: In function 'void dfs(int, int, int)':
swap.cpp:73:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   73 |     for (auto [it,w] : g[p]) if (it!=q) dfs(it,p,w);
      |               ^
swap.cpp: In function 'void tfs(int, int)':
swap.cpp:80:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   80 |     for (auto [it,w] : g[p]) if (it!=q)
      |               ^
swap.cpp: In function 'void build(int)':
swap.cpp:92:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |         for (auto [it,w] : g[i]) temp.pb(w);
      |                   ^
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:169:35: warning: unused variable 'w' [-Wunused-variable]
  169 |         int a=it.yy.xx,b=it.yy.yy,w=it.xx;
      |                                   ^
swap.cpp:170:13: warning: unused variable 'c' [-Wunused-variable]
  170 |         int c=Lca(a,b,nebitno,nebitno);
      |             ^

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27