제출 #725246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
725246		n0sk1ll	자매 도시 (APIO20_swap)	C++14	30 / 100	510 ms	41124 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];
int dp[100005]; //min twe u subtree
int VREME=0;

vector<vector<pii>> uopste(100005);

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 build(int n)
{
    ff(i,0,n)
    {
        vector<int> temp;
        for (auto [it,w] : uopste[i]) temp.pb(w);

        if ((int)temp.size()<3) dp[i]=mod;
        else sort(all(temp)),dp[i]=temp[2];
    }

    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]]);
    }
}

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

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

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

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

    a=up[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) uopste[u[i]].pb({v[i],w[i]}),uopste[v[i]].pb({u[i],w[i]});
    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);
    }

    ff(i,0,n) dp[i]=mod;
    dfs(0,0,0);
    build(n);

    vector<bool> vis(n,false);
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    ff(i,0,n) pq.push({dp[i],i});

    while (!pq.empty())
    {
        auto [d,p]=pq.top();
        pq.pop();

        if (vis[p]) continue;
        vis[p]=true;

        dp[p]=d;
        for (auto [it,w] : uopste[p]) pq.push({max(d,w),it});
    }
}

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

/*

4 4
0 1 1
1 2 2
2 3 3
3 0 4
4
0 1
1 2
2 3
3 0

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


*/

컴파일 시 표준 에러 (stderr) 메시지

swap.cpp: In function 'void dfs(int, int, int)':
swap.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for (auto [it,w] : g[p]) if (it!=q) dfs(it,p,w);
      |               ^
swap.cpp: In function 'void build(int)':
swap.cpp:84:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |         for (auto [it,w] : uopste[i]) temp.pb(w);
      |                   ^
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:157:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  157 |         auto [d,p]=pq.top();
      |              ^
swap.cpp:164:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  164 |         for (auto [it,w] : uopste[p]) pq.push({max(d,w),it});
      |                   ^

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