oj.uz

Submission #560304

# Submission time Handle Problem Language Result Execution time Memory
560304 2022-05-11T09:10:22 Z TrungNotChung Swapping Cities (APIO20_swap) C++11
0 / 100
 2000 ms 47604 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] , b[N];
int h[N] , f[N][logn+1] , g[N][logn+1];
vector<pii> adj1[N] , adj2[N];
bool mark1[M] , mark2[N];

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)
{
    b[u] = prv;
    if(u != 0)
    {
        for(int i=0 ; i<(int)adj2[par[u]].size() ; ++i)
        {
            int id = adj2[par[u]][i].se;
            if(id != b[par[u]] && id != prv)
            {
                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));
        }
    }
    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)
{
    int x = u , y = v;
    for(int i=0 ; i<m ; ++i) mark1[i] = false;
    for(int i=0 ; i<n ; ++i) mark2[i] = false;
    if(h[u] < h[v]) swap(u , v);
    while(h[u] > h[v])
    {
        mark2[u] = true;
        mark1[b[u]] = true;
        u = par[u];
    }
    while(u != v)
    {
        mark2[u] = mark2[v] = true;
        mark1[b[u]] = mark1[b[v]] = true;
        u = par[u] , v = par[v];
    }
    mark2[u] = true;
    for(int i=0 ; i<m ; ++i)
    {
        if(mark1[i]) continue;
        if(mark2[edges[i].u] && edges[i].u != x && edges[i].u != y) return edges[i].w;
        if(mark2[edges[i].v] && edges[i].v != x && edges[i].v != y) return edges[i].w;
    }
    return INF;
}

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14488 KB Output is correct
5 Correct 7 ms 14676 KB Output is correct
6 Correct 7 ms 14724 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14804 KB Output is correct
9 Correct 139 ms 38104 KB Output is correct
10 Correct 186 ms 44744 KB Output is correct
11 Correct 183 ms 43788 KB Output is correct
12 Correct 202 ms 45800 KB Output is correct
13 Correct 175 ms 47604 KB Output is correct
14 Execution timed out 2100 ms 37580 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Incorrect 1012 ms 43148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14488 KB Output is correct
5 Correct 7 ms 14676 KB Output is correct
6 Correct 7 ms 14724 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14804 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14676 KB Output is correct
11 Correct 8 ms 14676 KB Output is correct
12 Correct 8 ms 14648 KB Output is correct
13 Correct 8 ms 14648 KB Output is correct
14 Correct 8 ms 14628 KB Output is correct
15 Incorrect 8 ms 14636 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14488 KB Output is correct
6 Correct 7 ms 14676 KB Output is correct
7 Correct 7 ms 14724 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14804 KB Output is correct
10 Correct 139 ms 38104 KB Output is correct
11 Correct 186 ms 44744 KB Output is correct
12 Correct 183 ms 43788 KB Output is correct
13 Correct 202 ms 45800 KB Output is correct
14 Correct 175 ms 47604 KB Output is correct
15 Correct 8 ms 14676 KB Output is correct
16 Correct 8 ms 14676 KB Output is correct
17 Correct 8 ms 14648 KB Output is correct
18 Correct 8 ms 14648 KB Output is correct
19 Correct 8 ms 14628 KB Output is correct
20 Incorrect 8 ms 14636 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14488 KB Output is correct
5 Correct 7 ms 14676 KB Output is correct
6 Correct 7 ms 14724 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14804 KB Output is correct
9 Correct 139 ms 38104 KB Output is correct
10 Correct 186 ms 44744 KB Output is correct
11 Correct 183 ms 43788 KB Output is correct
12 Correct 202 ms 45800 KB Output is correct
13 Correct 175 ms 47604 KB Output is correct
14 Execution timed out 2100 ms 37580 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 7 ms 14488 KB Output is correct
6 Correct 7 ms 14676 KB Output is correct
7 Correct 7 ms 14724 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14804 KB Output is correct
10 Correct 139 ms 38104 KB Output is correct
11 Correct 186 ms 44744 KB Output is correct
12 Correct 183 ms 43788 KB Output is correct
13 Correct 202 ms 45800 KB Output is correct
14 Correct 175 ms 47604 KB Output is correct
15 Execution timed out 2100 ms 37580 KB Time limit exceeded
16 Halted 0 ms 0 KB -