oj.uz

답안 #965774

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965774 2024-04-19T07:16:16 Z owoovo 자매 도시 (APIO20_swap) C++17
13 / 100
 183 ms 31888 KB 
#include "swap.h"
#include<bits/stdc++.h>
#define ll long long 
#define F first 
#define S second 
using namespace std;
const int maxn=1e9+10;
int deg[100010],tag[100010],wh[100010],dep[100010],jpt[100010][20],jpw[100010][20];
vector<int> e[100010];
struct Dsu{
    int ori[100010]={},si[100010]={};
    void init(int n){
        for(int i=0;i<n;i++)ori[i]=i,si[i]=1;
        return ;
    }
    int f(int a){
        return a==ori[a]?a:f(ori[a]);
    }
    void onion(int a,int b,int w){
        int ok=0;
        if(deg[a]>=3||deg[b]>=3)ok=1;
        a=f(a),b=f(b);
        if(a==b){
            wh[a]=min(wh[a],w);
            return ;
        }
        if(si[a]>si[b])swap(a,b);
        si[b]+=si[a];
        ori[a]=b;
        jpt[a][0]=b;
        jpw[a][0]=w;
        if(ok)wh[b]=min(wh[b],w);
        e[a].push_back(b),e[b].push_back(a);
        return;
    }
}dsu;
void dfs(int now,int last,int w){
    w=min(w,wh[now]);
    wh[now]=min(w,wh[now]);
    dep[now]=dep[last]+1;
    for(auto x:e[now]){
        if(x==last)continue;
        dfs(x,now,w);
        wh[now]=min(wh[x],wh[now]);
    }
    return;
}
void init(int n, int m,vector<int> u, vector<int> v, vector<int> w) {
    for(int i=0;i<n;i++)wh[i]=maxn;
    dsu.init(n);
    vector<pair<int,pair<int,int>>>edge;
    for(int i=0;i<m;i++)edge.push_back({w[i],{u[i],v[i]}});
    sort(edge.begin(),edge.end());
    for(auto [x,y]:edge){
        auto [q,r]=y;
        deg[q]++;
        deg[r]++;
        dsu.onion(q,r,x);
    }
    for(int i=1;i<=18;i++){
        for(int j=0;j<n;j++){
            jpt[j][i]=jpt[jpt[j][i-1]][i-1];
            jpw[j][i]=max(jpw[j][i-1],jpw[jpt[j][i-1]][i-1]);
        }
    }
    for(int i=0;i<n;i++)if(i==dsu.ori[i])dfs(i,i,maxn);
}
int lca(int u,int v){
    if(dep[u]<dep[v])swap(u,v);
    int ans=0;
    for(int i=18;i>=0;i--){
        if(dep[u]-(1<<i)>=dep[v]){
            //cout<<jpw[u][i]<<" "<<u<<" k\n";
            ans=max(ans,jpw[u][i]);
            u=jpt[u][i];
        }
    }
    if(u==v){
        //cout<<ans<<" "<<wh[u]<<"\n";

        return max(ans,wh[u]);
    }
    for(int i=18;i>=0;i--){
        if(jpt[u][i]!=jpt[v][i]){
            ans=max(ans,jpw[u][i]);
            ans=max(ans,jpw[v][i]);
            u=jpt[u][i];
            v=jpt[v][i];
        }
    }
    ans=max(ans,jpw[u][0]);
    ans=max(ans,jpw[v][0]);
    u=jpt[u][0];
    //cout<<ans<<" "<<wh[u]<<"\n";
    return max(ans,wh[u]);
}
int getMinimumFuelCapacity(int u, int v) {
    int ans=lca(u,v);
    return ans==maxn?-1:ans;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6688 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 56 ms 26724 KB Output is correct
10 Correct 67 ms 28104 KB Output is correct
11 Correct 70 ms 27848 KB Output is correct
12 Correct 70 ms 28868 KB Output is correct
13 Correct 64 ms 28836 KB Output is correct
14 Correct 72 ms 26648 KB Output is correct
15 Correct 151 ms 30728 KB Output is correct
16 Correct 146 ms 30324 KB Output is correct
17 Correct 178 ms 31428 KB Output is correct
18 Correct 159 ms 31428 KB Output is correct
19 Correct 61 ms 14444 KB Output is correct
20 Correct 158 ms 30888 KB Output is correct
21 Correct 148 ms 31032 KB Output is correct
22 Correct 160 ms 31828 KB Output is correct
23 Correct 142 ms 31888 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 156 ms 30964 KB Output is correct
4 Correct 183 ms 31276 KB Output is correct
5 Correct 145 ms 31216 KB Output is correct
6 Correct 138 ms 30832 KB Output is correct
7 Correct 137 ms 31168 KB Output is correct
8 Correct 137 ms 30716 KB Output is correct
9 Correct 164 ms 31132 KB Output is correct
10 Correct 139 ms 31040 KB Output is correct

Subtask #3
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6688 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 2 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 3 ms 6492 KB Output is correct
13 Correct 2 ms 6608 KB Output is correct
14 Correct 2 ms 6492 KB Output is correct
15 Incorrect 2 ms 6492 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6688 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 56 ms 26724 KB Output is correct
11 Correct 67 ms 28104 KB Output is correct
12 Correct 70 ms 27848 KB Output is correct
13 Correct 70 ms 28868 KB Output is correct
14 Correct 64 ms 28836 KB Output is correct
15 Correct 2 ms 6492 KB Output is correct
16 Correct 2 ms 6492 KB Output is correct
17 Correct 3 ms 6492 KB Output is correct
18 Correct 2 ms 6608 KB Output is correct
19 Correct 2 ms 6492 KB Output is correct
20 Incorrect 2 ms 6492 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6688 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 56 ms 26724 KB Output is correct
10 Correct 67 ms 28104 KB Output is correct
11 Correct 70 ms 27848 KB Output is correct
12 Correct 70 ms 28868 KB Output is correct
13 Correct 64 ms 28836 KB Output is correct
14 Correct 72 ms 26648 KB Output is correct
15 Correct 151 ms 30728 KB Output is correct
16 Correct 146 ms 30324 KB Output is correct
17 Correct 178 ms 31428 KB Output is correct
18 Correct 159 ms 31428 KB Output is correct
19 Correct 156 ms 30964 KB Output is correct
20 Correct 183 ms 31276 KB Output is correct
21 Correct 145 ms 31216 KB Output is correct
22 Correct 138 ms 30832 KB Output is correct
23 Correct 137 ms 31168 KB Output is correct
24 Correct 137 ms 30716 KB Output is correct
25 Correct 164 ms 31132 KB Output is correct
26 Correct 139 ms 31040 KB Output is correct
27 Correct 2 ms 6492 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 3 ms 6492 KB Output is correct
30 Correct 2 ms 6608 KB Output is correct
31 Correct 2 ms 6492 KB Output is correct
32 Incorrect 2 ms 6492 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6688 KB Output is correct
9 Correct 2 ms 6492 KB Output is correct
10 Correct 56 ms 26724 KB Output is correct
11 Correct 67 ms 28104 KB Output is correct
12 Correct 70 ms 27848 KB Output is correct
13 Correct 70 ms 28868 KB Output is correct
14 Correct 64 ms 28836 KB Output is correct
15 Correct 72 ms 26648 KB Output is correct
16 Correct 151 ms 30728 KB Output is correct
17 Correct 146 ms 30324 KB Output is correct
18 Correct 178 ms 31428 KB Output is correct
19 Correct 159 ms 31428 KB Output is correct
20 Correct 156 ms 30964 KB Output is correct
21 Correct 183 ms 31276 KB Output is correct
22 Correct 145 ms 31216 KB Output is correct
23 Correct 138 ms 30832 KB Output is correct
24 Correct 137 ms 31168 KB Output is correct
25 Correct 137 ms 30716 KB Output is correct
26 Correct 164 ms 31132 KB Output is correct
27 Correct 139 ms 31040 KB Output is correct
28 Correct 2 ms 6492 KB Output is correct
29 Correct 2 ms 6492 KB Output is correct
30 Correct 3 ms 6492 KB Output is correct
31 Correct 2 ms 6608 KB Output is correct
32 Correct 2 ms 6492 KB Output is correct
33 Incorrect 2 ms 6492 KB Output isn't correct
34 Halted 0 ms 0 KB -