oj.uz

Submission #977264

# Submission time Handle Problem Language Result Execution time Memory
977264 2024-05-07T15:21:03 Z imarn Swapping Cities (APIO20_swap) C++14
6 / 100
 207 ms 49552 KB 
#include<bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define sz(x) (ll)x.size()
using namespace std;
const int mxn=3e5+5;
vector<int>g[mxn];
int pr[mxn]{0},cur,d[mxn]{0},dp[mxn]{0},dep[mxn]{0},up[mxn][20]{0};
bool cyc[mxn]{0},ok=0;
int get(int r){
    return pr[r]==r?r:pr[r]=get(pr[r]);
}
void dfs(int u,int p,int l){
    up[u][0]=p;dep[u]=l;
    for(int i=1;i<20;i++)up[u][i]=up[up[u][i-1]][i-1];
    for(auto v:g[u]){
        if(v==p)continue;
        if(!cyc[v])dp[v]=dp[u];
        dfs(v,u,l+1);
    }
}
int qr(int a,int b){
    if(dep[a]>dep[b])swap(a,b);
    for(int i=19;i>=0;i--)if(dep[b]-(1<<i)>=dep[a])b=up[b][i];
    if(a==b)return dp[b];
    for(int i=19;i>=0;i--)if(up[a][i]!=up[b][i])a=up[a][i],b=up[b][i];
    return dp[up[a][0]];
}
void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W){
    cur=N;iota(pr,pr+mxn,0);vector<pair<int,pii>>ed;
    for(int i=0;i<M;i++){
        ed.pb({W[i],{U[i],V[i]}});
        d[U[i]]++,d[V[i]]++;
    }sort(ed.begin(),ed.end());
    for(auto it : ed){
        if(get(it.s.f)==get(it.s.s)){
            g[cur].pb(get(it.s.f));pr[get(it.s.f)]=cur;
            dp[cur]=it.f;cyc[cur++]=1;
        }else{
            int u=get(it.s.f),v=get(it.s.s);
            g[cur].pb(u);g[cur].pb(v);
            pr[u]=pr[v]=cur;dp[cur]=it.f;
            if(cyc[u]||cyc[v]||d[it.s.f]>=3||d[it.s.s]>=3)cyc[cur]=1;
            cur++;
        }
    }cur--;dfs(cur,cur,0);if(cyc[cur])ok=1;
}
int getMinimumFuelCapacity(int X, int Y){
    if(!ok)return -1;
    else return qr(X,Y);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15284 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 15196 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 72 ms 34464 KB Output is correct
10 Correct 95 ms 37840 KB Output is correct
11 Correct 88 ms 37696 KB Output is correct
12 Correct 100 ms 38172 KB Output is correct
13 Correct 80 ms 42184 KB Output is correct
14 Correct 75 ms 34760 KB Output is correct
15 Correct 139 ms 41716 KB Output is correct
16 Correct 128 ms 41416 KB Output is correct
17 Correct 134 ms 41928 KB Output is correct
18 Correct 124 ms 46020 KB Output is correct
19 Correct 65 ms 23636 KB Output is correct
20 Correct 166 ms 41928 KB Output is correct
21 Correct 169 ms 41932 KB Output is correct
22 Correct 179 ms 42388 KB Output is correct
23 Correct 207 ms 46484 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 167 ms 49040 KB Output is correct
4 Incorrect 191 ms 49552 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15284 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 15196 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Incorrect 3 ms 15196 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 15196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 15196 KB Output is correct
2 Correct 3 ms 15196 KB Output is correct
3 Correct 3 ms 15196 KB Output is correct
4 Correct 3 ms 15284 KB Output is correct
5 Correct 3 ms 15196 KB Output is correct
6 Correct 4 ms 15196 KB Output is correct
7 Correct 3 ms 15196 KB Output is correct
8 Correct 3 ms 15196 KB Output is correct
9 Correct 72 ms 34464 KB Output is correct
10 Correct 95 ms 37840 KB Output is correct
11 Correct 88 ms 37696 KB Output is correct
12 Correct 100 ms 38172 KB Output is correct
13 Correct 80 ms 42184 KB Output is correct
14 Correct 75 ms 34760 KB Output is correct
15 Correct 139 ms 41716 KB Output is correct
16 Correct 128 ms 41416 KB Output is correct
17 Correct 134 ms 41928 KB Output is correct
18 Correct 124 ms 46020 KB Output is correct
19 Correct 167 ms 49040 KB Output is correct
20 Incorrect 191 ms 49552 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 15196 KB Output isn't correct
2 Halted 0 ms 0 KB -