oj.uz

Submission #751866

# Submission time Handle Problem Language Result Execution time Memory
751866 2023-06-01T17:09:50 Z snpmrnhlol Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 33976 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = 2e5;
const int inf = 2e9;
int id[M],deg[N];
struct nodedata
{
    int parent,active;
};
vector <nodedata> nodes;///parent,active
vector <int> e[2*N - 1];
int p2[2*N - 1][20];
int dpth[2*N - 1];
struct dsu
{
    int id,parent,active,sz;
};
dsu v[N];
int leader(int node)
{
    if(node == v[node].parent)return node;
    int l = leader(v[node].parent);
    v[node].parent = l;
    return v[node].parent;
}
void connect(int a,int b,int w)
{
    deg[a]++;
    deg[b]++;
    int active = 0;
    if(deg[a] >= 3 || deg[b] >= 3)active = 1;
    a = leader(a);
    b = leader(b);
    if(a == b)
    {
        if(nodes[v[a].id].active == inf)nodes[v[a].id].active = w;
        v[a].active = min(v[a].active,w);
    }
    else
    {
        nodes[v[a].id].parent = nodes.size();
        nodes[v[b].id].parent = nodes.size();
        if(v[a].active != inf || v[b].active != inf)active = 1;
        if(v[a].sz < v[b].sz)swap(a,b);
        v[b].parent = a;
        v[a].sz+=v[b].sz;
        v[a].id = nodes.size();
        nodes.push_back({-1,active?w:inf});
        v[a].active = max(min(v[b].active,v[a].active),w);
        nodes[a].active = v[a].active;
    }
}
void dfs(int node,int p = -1,int d = 0)
{
    dpth[node] = d;
    p2[node][0] = p;
    for(auto i:e[node])
    {
        if(i == p)continue;
        dfs(i,node,d + 1);
    }
}
void init(int n, int m,vector<int> u,vector<int> u2,vector<int> w)
{
    int i,j;
    for(i = 0; i < m; i++)id[i] = i;
    for(i = 0; i < n; i++)
    {
        nodes.push_back({-1,inf});
        v[i] = {i,i,inf,1};
    }
    sort(id,id + m,[&](int a,int b)
    {
        return w[a] < w[b];
    });
    for(i = 0; i < m; i++)
    {
        ///connect u[id[i]] with v[id[i]]
        connect(u[id[i]],u2[id[i]],w[id[i]]);
        //cout<<u[id[i]]<<' '<<u2[id[i]]<<'\n';
    }
    int cnt = 0;
    for(auto i:nodes)
    {
        if(i.parent != -1)
        {
            e[i.parent].push_back(cnt);
        }
        cnt++;
    }
    dfs(nodes.size() - 1,nodes.size() - 1);
    for(j = 1; j < 20; j++)
    {
        for(i = 0; i < 2*n - 1; i++)
        {
            p2[i][j] = p2[p2[i][j - 1]][j - 1];
        }
    }
    /*for(i = 0;i < 2*n - 1;i++){
        for(j = 0;j < 20;j++)cout<<p2[i][j]<<' ';
        cout<<'\n';
    }
    for(i = 0;i < 2*n - 1;i++){
        cout<<p2[i][0]<<' '<<dpth[i]<<' '<<nodes[i].active<<' '<<i<<'\n';
    }*/
}

int getMinimumFuelCapacity(int x, int y)
{
    if(nodes[nodes.size() - 1].active == inf)return -1;
    if(dpth[x] < dpth[y])swap(x,y);
    /*for(int i = 19; i >= 0; i--)
    {
        if(dpth[x] - (1<<i) >= dpth[y])
        {
            x = p2[x][i];
        }
    }
    for(int i = 19; i >= 0; i--)
    {
        if(p2[x][i] != p2[y][i])
        {
            x = p2[x][i];
            y = p2[y][i];
        }
    }
    if(x != y)x = p2[x][0];
    for(int i = 19; i >= 0; i--)
    {
        if(nodes[p2[x][i]].active == inf)
        {
            x = p2[x][i];
        }
    }
    if(nodes[x].active == inf)
    {
        x = p2[x][0];
    }*/
    while(dpth[x] > dpth[y])x = p2[x][0];
    while(x != y)x = p2[x][0],y = p2[y][0];
    while(nodes[x].active == inf)x = p2[x][0];
    return nodes[x].active;
}
/**
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
**/

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 86 ms 25252 KB Output is correct
10 Correct 117 ms 29800 KB Output is correct
11 Correct 104 ms 29412 KB Output is correct
12 Correct 122 ms 30748 KB Output is correct
13 Correct 114 ms 32148 KB Output is correct
14 Correct 90 ms 25384 KB Output is correct
15 Correct 159 ms 31720 KB Output is correct
16 Correct 177 ms 31144 KB Output is correct
17 Correct 166 ms 32512 KB Output is correct
18 Correct 157 ms 33920 KB Output is correct
19 Correct 88 ms 12464 KB Output is correct
20 Correct 257 ms 33064 KB Output is correct
21 Correct 259 ms 32252 KB Output is correct
22 Correct 311 ms 33976 KB Output is correct
23 Execution timed out 2068 ms 33792 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Execution timed out 2053 ms 33464 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 5272 KB Output is correct
11 Incorrect 3 ms 5204 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 86 ms 25252 KB Output is correct
11 Correct 117 ms 29800 KB Output is correct
12 Correct 104 ms 29412 KB Output is correct
13 Correct 122 ms 30748 KB Output is correct
14 Correct 114 ms 32148 KB Output is correct
15 Correct 3 ms 5272 KB Output is correct
16 Incorrect 3 ms 5204 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5076 KB Output is correct
5 Correct 3 ms 5204 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 86 ms 25252 KB Output is correct
10 Correct 117 ms 29800 KB Output is correct
11 Correct 104 ms 29412 KB Output is correct
12 Correct 122 ms 30748 KB Output is correct
13 Correct 114 ms 32148 KB Output is correct
14 Correct 90 ms 25384 KB Output is correct
15 Correct 159 ms 31720 KB Output is correct
16 Correct 177 ms 31144 KB Output is correct
17 Correct 166 ms 32512 KB Output is correct
18 Correct 157 ms 33920 KB Output is correct
19 Execution timed out 2053 ms 33464 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 86 ms 25252 KB Output is correct
11 Correct 117 ms 29800 KB Output is correct
12 Correct 104 ms 29412 KB Output is correct
13 Correct 122 ms 30748 KB Output is correct
14 Correct 114 ms 32148 KB Output is correct
15 Correct 90 ms 25384 KB Output is correct
16 Correct 159 ms 31720 KB Output is correct
17 Correct 177 ms 31144 KB Output is correct
18 Correct 166 ms 32512 KB Output is correct
19 Correct 157 ms 33920 KB Output is correct
20 Execution timed out 2053 ms 33464 KB Time limit exceeded
21 Halted 0 ms 0 KB -