oj.uz

답안 #865053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
865053 2023-10-24T04:41:51 Z jk410 자매 도시 (APIO20_swap) C++17
6 / 100
 142 ms 43380 KB 
#include "swap.h"
#include <vector>
#include <algorithm>
#include <functional>
#define all(v) v.begin(),v.end()
using namespace std;
struct edge{
    int u,v,cost;
};
struct node{
    int cost;
    bool flag;
};
const int MAX=18;
vector<node> nodes;
vector<vector<int>> child;
vector<int> depth;
vector<vector<int>> par(MAX+1);
vector<int> ans;
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    vector<edge> edges(M);
    vector<int> group(N+M);
    vector<int> deg(N);
    nodes.resize(N+M);
    child.resize(N+M);
    depth.resize(N+M);
    for (int i=0; i<=MAX; i++)
        par[i].resize(N+M);
    ans.resize(N+M);
    for (int i=0; i<M; i++)
        edges[i]={U[i],V[i],W[i]};
    sort(all(edges),[&](edge a,edge b)->bool{
        return a.cost<b.cost;
    });
    for (int i=0; i<N+M; i++){
        group[i]=i;
        nodes[i]={0,false};
        par[0][i]=i;
    }
    function<int(int)> getGroup=[&](int v)->int{
        if (group[v]==v)
            return v;
        return group[v]=getGroup(group[v]);
    };
    for (int i=0; i<M; i++){
        edge e=edges[i];
        nodes[i+N].cost=e.cost;
        deg[e.u]++;
        deg[e.v]++;
        int u=getGroup(e.u),v=getGroup(e.v);
        if (deg[e.u]>2||deg[e.v]>2||nodes[u].flag||nodes[v].flag)
            nodes[i+N].flag=true;
        if (u==v){
            group[u]=i+N;
            child[i+N].push_back(u);
            par[0][u]=i+N;
            nodes[i+N].flag=true;
            continue;
        }
        group[u]=group[v]=i+N;
        child[i+N].push_back(u);
        child[i+N].push_back(v);
        par[0][u]=par[0][v]=i+N;
    }
    for (int t=1; t<=MAX; t++){
        for (int i=0; i<N; i++)
            par[t][i]=par[t-1][par[t-1][i]];
    }
    function<void(int)> dfs=[&](int v){
        for (int i:child[v]){
            depth[i]=depth[v]+1;
            ans[i]=(nodes[i].flag?nodes[i].cost:ans[v]);
            dfs(i);
        }
    };
    for (int i=0; i<N+M; i++){
        if (par[0][i]!=i)
            continue;
        ans[i]=(nodes[i].flag?nodes[i].cost:-1);
        dfs(i);
    }
}
int getLCA(int u,int v){
    if (depth[u]>depth[v])
        swap(u,v);
    for (int i=0,t=depth[v]-depth[u]; t; i++,t>>=1){
        if (t&1)
            v=par[i][v];
    }
    if (u==v)
        return u;
    for (int t=MAX; t>=0; t--){
        if (par[t][u]!=par[t][v]){
            u=par[t][u];
            v=par[t][v];
        }
    }
    return par[0][u];
}
int getMinimumFuelCapacity(int X, int Y){
    return ans[getLCA(X,Y)];
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 424 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 48 ms 26028 KB Output is correct
10 Correct 68 ms 31568 KB Output is correct
11 Correct 59 ms 31276 KB Output is correct
12 Correct 61 ms 33108 KB Output is correct
13 Correct 54 ms 37824 KB Output is correct
14 Correct 52 ms 26196 KB Output is correct
15 Correct 124 ms 35664 KB Output is correct
16 Correct 142 ms 34768 KB Output is correct
17 Correct 130 ms 36948 KB Output is correct
18 Correct 129 ms 41928 KB Output is correct
19 Correct 52 ms 10392 KB Output is correct
20 Correct 125 ms 35664 KB Output is correct
21 Correct 131 ms 34632 KB Output is correct
22 Correct 126 ms 37068 KB Output is correct
23 Correct 129 ms 41556 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 120 ms 43380 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 424 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Incorrect 1 ms 604 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 48 ms 26028 KB Output is correct
11 Correct 68 ms 31568 KB Output is correct
12 Correct 59 ms 31276 KB Output is correct
13 Correct 61 ms 33108 KB Output is correct
14 Correct 54 ms 37824 KB Output is correct
15 Incorrect 1 ms 604 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 424 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 696 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 48 ms 26028 KB Output is correct
10 Correct 68 ms 31568 KB Output is correct
11 Correct 59 ms 31276 KB Output is correct
12 Correct 61 ms 33108 KB Output is correct
13 Correct 54 ms 37824 KB Output is correct
14 Correct 52 ms 26196 KB Output is correct
15 Correct 124 ms 35664 KB Output is correct
16 Correct 142 ms 34768 KB Output is correct
17 Correct 130 ms 36948 KB Output is correct
18 Correct 129 ms 41928 KB Output is correct
19 Incorrect 120 ms 43380 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 696 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 48 ms 26028 KB Output is correct
11 Correct 68 ms 31568 KB Output is correct
12 Correct 59 ms 31276 KB Output is correct
13 Correct 61 ms 33108 KB Output is correct
14 Correct 54 ms 37824 KB Output is correct
15 Correct 52 ms 26196 KB Output is correct
16 Correct 124 ms 35664 KB Output is correct
17 Correct 142 ms 34768 KB Output is correct
18 Correct 130 ms 36948 KB Output is correct
19 Correct 129 ms 41928 KB Output is correct
20 Incorrect 120 ms 43380 KB Output isn't correct
21 Halted 0 ms 0 KB -