oj.uz

Submission #751861

# Submission time Handle Problem Language Result Execution time Memory
751861 2023-06-01T17:03:46 Z snpmrnhlol Swapping Cities (APIO20_swap) C++17
0 / 100
 2000 ms 34068 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 = inf;
    if(deg[a] >= 3 || deg[b] >= 3)active = min(active,w);
    a = leader(a);
    b = leader(b);
    if(a == b)
    {
        nodes[v[a].id].active = min(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].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});
        v[a].active = min(v[b].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 4992 KB Output is correct
2 Correct 3 ms 5036 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 5164 KB Output is correct
6 Correct 4 ms 5256 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 95 ms 25276 KB Output is correct
10 Correct 120 ms 29832 KB Output is correct
11 Correct 115 ms 29380 KB Output is correct
12 Correct 152 ms 30828 KB Output is correct
13 Correct 122 ms 32228 KB Output is correct
14 Correct 94 ms 25268 KB Output is correct
15 Correct 159 ms 31720 KB Output is correct
16 Correct 152 ms 31084 KB Output is correct
17 Correct 163 ms 32548 KB Output is correct
18 Correct 159 ms 34068 KB Output is correct
19 Correct 106 ms 12584 KB Output is correct
20 Correct 274 ms 32988 KB Output is correct
21 Correct 343 ms 32256 KB Output is correct
22 Correct 301 ms 33924 KB Output is correct
23 Execution timed out 2067 ms 33776 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 4992 KB Output is correct
2 Correct 3 ms 5036 KB Output is correct
3 Execution timed out 2060 ms 33580 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 4992 KB Output is correct
2 Correct 3 ms 5036 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 5164 KB Output is correct
6 Correct 4 ms 5256 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 4 ms 5204 KB Output is correct
11 Incorrect 4 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 4992 KB Output is correct
3 Correct 3 ms 5036 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 5164 KB Output is correct
7 Correct 4 ms 5256 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 95 ms 25276 KB Output is correct
11 Correct 120 ms 29832 KB Output is correct
12 Correct 115 ms 29380 KB Output is correct
13 Correct 152 ms 30828 KB Output is correct
14 Correct 122 ms 32228 KB Output is correct
15 Correct 4 ms 5204 KB Output is correct
16 Incorrect 4 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 4992 KB Output is correct
2 Correct 3 ms 5036 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 5164 KB Output is correct
6 Correct 4 ms 5256 KB Output is correct
7 Correct 3 ms 5204 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 95 ms 25276 KB Output is correct
10 Correct 120 ms 29832 KB Output is correct
11 Correct 115 ms 29380 KB Output is correct
12 Correct 152 ms 30828 KB Output is correct
13 Correct 122 ms 32228 KB Output is correct
14 Correct 94 ms 25268 KB Output is correct
15 Correct 159 ms 31720 KB Output is correct
16 Correct 152 ms 31084 KB Output is correct
17 Correct 163 ms 32548 KB Output is correct
18 Correct 159 ms 34068 KB Output is correct
19 Execution timed out 2060 ms 33580 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 4992 KB Output is correct
3 Correct 3 ms 5036 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 5164 KB Output is correct
7 Correct 4 ms 5256 KB Output is correct
8 Correct 3 ms 5204 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 95 ms 25276 KB Output is correct
11 Correct 120 ms 29832 KB Output is correct
12 Correct 115 ms 29380 KB Output is correct
13 Correct 152 ms 30828 KB Output is correct
14 Correct 122 ms 32228 KB Output is correct
15 Correct 94 ms 25268 KB Output is correct
16 Correct 159 ms 31720 KB Output is correct
17 Correct 152 ms 31084 KB Output is correct
18 Correct 163 ms 32548 KB Output is correct
19 Correct 159 ms 34068 KB Output is correct
20 Execution timed out 2060 ms 33580 KB Time limit exceeded
21 Halted 0 ms 0 KB -