oj.uz

Submission #560259

# Submission time Handle Problem Language Result Execution time Memory
560259 2022-05-11T08:16:05 Z TrungNotChung Swapping Cities (APIO20_swap) C++11
0 / 100
 2000 ms 51864 KB 
//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  
#include "swap.h"

using namespace std;

const int N = (int)1e5+228;
const int M = (int)2e5+228;
const int INF = (int)1e9+7;
const int logn = 17;

int n , m , par[N] , dad[N][logn+1];
int h[N] , f[N][logn+1] , g[N][logn+1];
vector<pii> adj1[N] , adj2[N];
bool mark[M];

struct edge
{
    int u , v , w;
    bool operator < (const edge &x) const
    {
        return w < x.w;
    }
}edges[M];

struct DisjointSet
{
    vector<int> lab;
    int n;
    DisjointSet(int _n = 0)
    {
        n = _n;
        lab.assign(n+7 , -1);
    }
    int Find(int u)
    {
        if(lab[u] < 0) return u;
        return lab[u] = Find(lab[u]);
    }
    bool join(int u , int v)
    {
        u = Find(u) , v = Find(v);
        if(u == v) return false;
        if(lab[u] < lab[v]) swap(u , v);
        lab[v] += lab[u] , lab[u] = v;
        return true;
    }
}dsu;

void dfs(int u , int prv)
{
    f[u][0] = INF;
    for(int i=0 ; i<(int)adj2[u].size() ; ++i)
    {
        int v = adj2[u][i].fi , id = adj2[u][i].se;
        if(mark[id]) continue;
        f[u][0] = edges[id].w;
        break;
    }
    for(int j=1 ; j<=logn ; ++j)
    {
        f[u][j] = min(f[u][j-1] , f[dad[u][j-1]][j-1]);
    }
    for(int i=0 ; i<(int)adj1[u].size() ; ++i)
    {
        int v = adj1[u][i].fi , id = adj1[u][i].se;
        if(id == prv || v == par[u]) continue;
        par[v] = u , h[v] = h[u] + 1 , dad[v][0] = u , g[v][0] = edges[id].w;
        for(int j=1 ; j<=logn ; ++j) 
        {
            dad[v][j] = dad[dad[v][j-1]][j-1];
            g[v][j] = max(g[v][j-1] , g[dad[v][j-1]][j-1]);
        }
        dfs(v , id); 
    }

}

void init(int _n, int _m,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = _n , m = _m;
    for(int i=0 ; i<m ; ++i) edges[i].u = U[i] , edges[i].v = V[i] , edges[i].w = W[i];
    sort(edges , edges+m);
    dsu = DisjointSet(n);
    for(int i=0 ; i<m ; ++i)
    {
        int u = edges[i].u , v = edges[i].v;
        adj2[u].push_back(make_pair(v , i));
        adj2[v].push_back(make_pair(u , i));
        if(dsu.join(u , v))
        {
            adj1[u].push_back(make_pair(v , i));
            adj1[v].push_back(make_pair(u , i));
            mark[i] = true;
        }
    }
    memset(f , 0x3f , sizeof(f));
    h[0] = 1;
    dfs(0 , -1);
    // for(int i=0 ; i<m ; ++i) cout << edges[i].w << " ";
    //     cout << '\n';
}

int getMin(int u , int v)
{
    if(u == v) return INF;
    if(h[u] < h[v]) swap(u , v);
    if(par[u] == v) return INF;
    u = par[u];
    int res = INF;
    for(int i=logn ; i>=0 ; --i)
    {
        if(h[dad[u][i]] >= h[v]) 
        {
            res = min(res , f[u][i]);
            u = dad[u][i];
        }
    }
    if(u == v) return res;
    res = min(res , f[u][0]) , u = dad[u][0] , v = dad[v][0];
    if(u == v) return res;
    for(int i=logn ; i>=0 ; --i)
    {
        if(dad[u][i] != dad[v][i])
        {
            res = min(res , f[u][i]);
            res = min(res , f[v][i]);
            u = dad[u][i] , v = dad[v][i];
        }
    }
    res = min(res , f[u][0]) , res = min(res , f[v][0]);
    return res;
}

int getMax(int u , int v)
{
    int res = 0;
    if(h[u] < h[v]) swap(u , v);
    for(int i=logn ; i>=0 ; --i) 
    {
        if(h[dad[u][i]] >= h[v])
        {
            res = max(res , g[u][i]);
            u = dad[u][i];
        }
    }
    if(u == v) return res;
    for(int i=logn ; i>=0 ; --i)
    {
        if(dad[u][i] != dad[v][i]) 
        {
            res = max(res , max(g[u][i] , g[v][i]));
            u = dad[u][i] , v = dad[v][i];
        }
    }
    res = max(res , max(g[u][0] , g[v][0]));
    return res;
}

vector<int> adj3[N];
int low[N] , num[N] , inID[N] , t , cur;
stack<int> st;

void tarjan(int u , int p)
{
    low[u] = num[u] = ++t;
    st.push(u);
    for(int v : adj3[u])
    {
        if(v == p) continue;
        if(num[v]) low[u] = min(low[u] , num[v]);
        else 
        {
            tarjan(v , u);
            low[u] = min(low[u] , low[v]);
        }
    }
    if(low[u] == num[u])
    {
        ++cur;
        int v;
        do 
        {
            v = st.top();
            st.pop();
            inID[v] = cur;
            low[v] = num[v] = INF;
        }
        while(u != v);
    }
}

bool check(int mid , int X , int Y)
{
    for(int i=0 ; i<n ; ++i) adj3[i].clear() , low[i] = num[i] = inID[i] = 0;
    t = 0 , cur = 0;
    for(int i=0 ; i<=mid ; ++i)
    {
        int u = edges[i].u , v = edges[i].v;
        adj3[u].push_back(v) , adj3[v].push_back(u);
    }
    for(int i=0 ; i<n ; ++i) if(!num[i]) tarjan(i , -1);
    return (inID[X] == inID[Y]);
}

int getMinimumFuelCapacity(int X, int Y) {
    int tmp1 = getMin(X , Y) , tmp2 = getMax(X , Y);
    int res = max(tmp1 , tmp2);
    if(m == n-1) 
    {
        if(res >= INF) return -1;
        return res;
    }
    int l = 0 , r = m-1 , tmp3 = INF;
    while(l <= r)
    {
        int mid = (l+r)/2;
        if(check(mid , X , Y))
        {
            tmp3 = edges[mid].w;
            r = mid-1;
        }
        else l = mid+1;
    }
    res = min(res , tmp3);
    if(res >= INF) return -1;
    return res;
}

Compilation message

swap.cpp: In function 'void dfs(int, int)':
swap.cpp:62:13: warning: unused variable 'v' [-Wunused-variable]
   62 |         int v = adj2[u][i].fi , id = adj2[u][i].se;
      |             ^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 8 ms 14564 KB Output is correct
5 Correct 8 ms 14676 KB Output is correct
6 Correct 8 ms 14640 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14696 KB Output is correct
9 Correct 146 ms 39528 KB Output is correct
10 Correct 245 ms 46532 KB Output is correct
11 Correct 191 ms 45532 KB Output is correct
12 Correct 191 ms 47532 KB Output is correct
13 Correct 215 ms 49364 KB Output is correct
14 Correct 193 ms 39204 KB Output is correct
15 Correct 623 ms 48872 KB Output is correct
16 Correct 645 ms 46456 KB Output is correct
17 Correct 556 ms 51864 KB Output is correct
18 Correct 580 ms 50268 KB Output is correct
19 Execution timed out 2064 ms 24268 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Incorrect 216 ms 44072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 8 ms 14564 KB Output is correct
5 Correct 8 ms 14676 KB Output is correct
6 Correct 8 ms 14640 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14696 KB Output is correct
9 Correct 8 ms 14404 KB Output is correct
10 Incorrect 8 ms 14676 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14404 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 8 ms 14424 KB Output is correct
5 Correct 8 ms 14564 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14640 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14696 KB Output is correct
10 Correct 146 ms 39528 KB Output is correct
11 Correct 245 ms 46532 KB Output is correct
12 Correct 191 ms 45532 KB Output is correct
13 Correct 191 ms 47532 KB Output is correct
14 Correct 215 ms 49364 KB Output is correct
15 Incorrect 8 ms 14676 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14420 KB Output is correct
2 Correct 9 ms 14420 KB Output is correct
3 Correct 8 ms 14424 KB Output is correct
4 Correct 8 ms 14564 KB Output is correct
5 Correct 8 ms 14676 KB Output is correct
6 Correct 8 ms 14640 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14696 KB Output is correct
9 Correct 146 ms 39528 KB Output is correct
10 Correct 245 ms 46532 KB Output is correct
11 Correct 191 ms 45532 KB Output is correct
12 Correct 191 ms 47532 KB Output is correct
13 Correct 215 ms 49364 KB Output is correct
14 Correct 193 ms 39204 KB Output is correct
15 Correct 623 ms 48872 KB Output is correct
16 Correct 645 ms 46456 KB Output is correct
17 Correct 556 ms 51864 KB Output is correct
18 Correct 580 ms 50268 KB Output is correct
19 Incorrect 216 ms 44072 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14404 KB Output is correct
2 Correct 8 ms 14420 KB Output is correct
3 Correct 9 ms 14420 KB Output is correct
4 Correct 8 ms 14424 KB Output is correct
5 Correct 8 ms 14564 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14640 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14696 KB Output is correct
10 Correct 146 ms 39528 KB Output is correct
11 Correct 245 ms 46532 KB Output is correct
12 Correct 191 ms 45532 KB Output is correct
13 Correct 191 ms 47532 KB Output is correct
14 Correct 215 ms 49364 KB Output is correct
15 Correct 193 ms 39204 KB Output is correct
16 Correct 623 ms 48872 KB Output is correct
17 Correct 645 ms 46456 KB Output is correct
18 Correct 556 ms 51864 KB Output is correct
19 Correct 580 ms 50268 KB Output is correct
20 Incorrect 216 ms 44072 KB Output isn't correct
21 Halted 0 ms 0 KB -