oj.uz

Submission #560292

# Submission time Handle Problem Language Result Execution time Memory
560292 2022-05-11T08:57:45 Z TrungNotChung Swapping Cities (APIO20_swap) C++11
0 / 100
 2000 ms 49360 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 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)
{
    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));
            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;
    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(par[u] == v) return res;
    if(h[u] > h[v]) res = min(res , f[u][0]) , u = dad[u][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];
        }
    }
    int w = par[u];
    for(int i=0 ; i<(int)adj2[w].size() ; ++i)
    {
        int id = adj2[w][i].se;
        if(id != b[u] && id != b[v])
        {
            res = min(res , edges[id].w);
            break;
        }
    }
    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;
}

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 14548 KB Output is correct
5 Correct 8 ms 14676 KB Output is correct
6 Correct 8 ms 14688 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14736 KB Output is correct
9 Correct 151 ms 38264 KB Output is correct
10 Correct 226 ms 44888 KB Output is correct
11 Correct 194 ms 43884 KB Output is correct
12 Correct 208 ms 45880 KB Output is correct
13 Correct 198 ms 47604 KB Output is correct
14 Correct 174 ms 37640 KB Output is correct
15 Correct 561 ms 46520 KB Output is correct
16 Correct 505 ms 44140 KB Output is correct
17 Correct 478 ms 49360 KB Output is correct
18 Correct 519 ms 47968 KB Output is correct
19 Execution timed out 2081 ms 22368 KB Time limit exceeded
20 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 209 ms 43096 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 14548 KB Output is correct
5 Correct 8 ms 14676 KB Output is correct
6 Correct 8 ms 14688 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14736 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 7 ms 14676 KB Output is correct
11 Correct 8 ms 14676 KB Output is correct
12 Correct 9 ms 14676 KB Output is correct
13 Correct 7 ms 14676 KB Output is correct
14 Correct 8 ms 14676 KB Output is correct
15 Incorrect 8 ms 14676 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 14548 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14688 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14736 KB Output is correct
10 Correct 151 ms 38264 KB Output is correct
11 Correct 226 ms 44888 KB Output is correct
12 Correct 194 ms 43884 KB Output is correct
13 Correct 208 ms 45880 KB Output is correct
14 Correct 198 ms 47604 KB Output is correct
15 Correct 7 ms 14676 KB Output is correct
16 Correct 8 ms 14676 KB Output is correct
17 Correct 9 ms 14676 KB Output is correct
18 Correct 7 ms 14676 KB Output is correct
19 Correct 8 ms 14676 KB Output is correct
20 Incorrect 8 ms 14676 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 14548 KB Output is correct
5 Correct 8 ms 14676 KB Output is correct
6 Correct 8 ms 14688 KB Output is correct
7 Correct 8 ms 14676 KB Output is correct
8 Correct 8 ms 14736 KB Output is correct
9 Correct 151 ms 38264 KB Output is correct
10 Correct 226 ms 44888 KB Output is correct
11 Correct 194 ms 43884 KB Output is correct
12 Correct 208 ms 45880 KB Output is correct
13 Correct 198 ms 47604 KB Output is correct
14 Correct 174 ms 37640 KB Output is correct
15 Correct 561 ms 46520 KB Output is correct
16 Correct 505 ms 44140 KB Output is correct
17 Correct 478 ms 49360 KB Output is correct
18 Correct 519 ms 47968 KB Output is correct
19 Incorrect 209 ms 43096 KB Output isn't correct
20 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 14548 KB Output is correct
6 Correct 8 ms 14676 KB Output is correct
7 Correct 8 ms 14688 KB Output is correct
8 Correct 8 ms 14676 KB Output is correct
9 Correct 8 ms 14736 KB Output is correct
10 Correct 151 ms 38264 KB Output is correct
11 Correct 226 ms 44888 KB Output is correct
12 Correct 194 ms 43884 KB Output is correct
13 Correct 208 ms 45880 KB Output is correct
14 Correct 198 ms 47604 KB Output is correct
15 Correct 174 ms 37640 KB Output is correct
16 Correct 561 ms 46520 KB Output is correct
17 Correct 505 ms 44140 KB Output is correct
18 Correct 478 ms 49360 KB Output is correct
19 Correct 519 ms 47968 KB Output is correct
20 Incorrect 209 ms 43096 KB Output isn't correct
21 Halted 0 ms 0 KB -