oj.uz

Submission #1088531

# Submission time Handle Problem Language Result Execution time Memory
1088531 2024-09-14T14:55:47 Z modwwe Swapping Cities (APIO20_swap) C++17
7 / 100
 101 ms 41656 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#include<bits/stdc++.h>
//#define int long long
//#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".ans","w",stdout)
#define pb push_back
#define checktime   cerr << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
using namespace std;
#define getchar_unlocked getchar

inline int scan()
{
    char c = getchar_unlocked();
    int x = 0;
    while(c<'0'||c>'9')
    {
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar_unlocked();
    }
    return x;
}

void phongbeo();
const int inf=1e9+1;
const int mod2=1e9+9;
const int  mod1=998244353;
struct icd
{
    long double a;
    int b;
};
struct ib
{
    int a;
    int b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
struct ie
{
    int a,b,c,d,e;

};

int n,m,s1,s2,s4,s3,sf,k,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0,dem=0,s33,dem3,dem4,l,r,mid,l2,r2,center;
int  i,s10,s12;
int kk;
int el=29;

bool cmp(ic a,ic b)
{
    return a.c<b.c;
}
struct dsu
{
    ib dsu[100001];
    void reset(int x)
    {
        dsu[x]= {1,x};
    }
    int get(int x)
    {
        if(dsu[x].b!=x) dsu[x].b=get(dsu[x].b);
        return dsu[x].b;
    }
    void noi(int x,int y)
    {
        if(dsu[x].a<dsu[y].a) swap(x,y);
        dsu[x].a+=dsu[y].a;
        dsu[y].b=x;
    }
} ds;
ic a[200001];
bool b[200001];
int st[17][100001];
int st2[17][100001];
int depth[100001];
int dp[100001];
int c[100001];
vector<ib> v[100001];
void dfs(int x,int y)
{
    st[0][x]=y;
    depth[x]=depth[y]+1;
    int s=inf,ss=inf,sss=inf;
   dp[x]=inf;
    for(auto f:v[x])
        if(f.a!=y)
        {
            if(f.b<s)sss=ss,ss=s,s=f.b;
            else if(f.b<ss) sss=ss,ss=f.b;
            else if(f.b<sss) sss=f.b;
            st2[0][f.a]=f.b,dfs(f.a,x);
            dp[x]=min(dp[x],max(dp[f.a],f.b));
        }
         if(v[x].size()>=3)dp[0]=1;
    dp[x]=min(dp[x],ss);
if(x!=1){
    ib f={0,st2[0][x]};
if(f.b<s)sss=ss,ss=s,s=f.b;
            else if(f.b<ss) sss=ss,ss=f.b;
            else if(f.b<sss) sss=f.b;}
                c[x]=sss;
    for(auto f:v[x])
    {
        if(f.a!=y)
        {
            dp[f.a]=min(dp[f.a],c[x]);
        }
    }
}
int lca(int x,int y)
{
    if(depth[x]<depth[y]) swap(x,y);
    int ss=depth[x]-depth[y];
    int s=0;
    ss--;

    if(ss>0)
        for(int j=0; j<17; ++j)
            if(bit(ss,j))
                s=max(s,st2[j][x]), x=st[j][x];
    if(ss!=-1)s=max(s,st2[0][x]);
    if(st[0][x]==y) return max(s,dp[x]);
    if(ss!=-1)x=st[0][x];
    for(int j=16; j>=0; --j)
        if(st[j][x]!=st[j][y])
            s=max({st2[j][x],st2[j][y],s}),x=st[j][x],y=st[j][y];
    s=max(s,st2[0][x]);
    s=max(s,st2[0][y]);
    s=max(s,min(dp[x],dp[y]));
    return s;
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    n=N;
    m=M;
    for(int i=1; i<=m; i++)
        a[i].a=U[i-1],a[i].b=V[i-1],a[i].c=W[i-1],a[i].a++,a[i].b++;
    for(int i=1; i<=n; i++)
        ds.reset(i);
    sort(a+1,a+1+m,cmp);
    bool de=0;
    s5=inf;
    for(int i=1; i<=m; i++)
    {
        s2=ds.get(a[i].a);
        s3=ds.get(a[i].b);
        if(s2!=s3)
        {
            v[a[i].a].pb({a[i].b,a[i].c});
            v[a[i].b].pb({a[i].a,a[i].c});
            ds.noi(s2,s3);
        }
        else b[i]=1;

    }
    dfs(1,0);
    for(int i=1; i<=m; i++)
        if(b[i])
            if(st[0][a[i].a]!=a[i].b&&st[0][a[i].b]!=a[i].a)
            {
                s5=a[i].c;
                break;
            }
    for(int i=1; i<17; i++)
        for(int j=1; j<=n; j++)
            st[i][j]=st[i-1][st[i-1][j]],
                     st2[i][j]=max(st2[i-1][j],st2[i-1][st[i-1][j]]);

}
int getMinimumFuelCapacity(int l, int r)
{
    if(dp[0]==0) return -1;
    l++;
    r++;
    return lca(l,r);
}
/*
main()
{
    freopen("test.inp","r",stdin);
    freopen("test.out","w",stdout);
    cin>>n>>m ;
    vector<int> a1,a2,a3;
    for(int i=1; i<=m; i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        a1.pb(x);
        a2.pb(y);
        a3.pb(z);
    }
    init(n,m,a1,a2,a3);
    cin>>m;
    while(m--)
    {
        int x,y;
        cin>>x>>y;
        cout<<getMinimumFuelCapacity(x,y)<<"\n";
    }
}*/

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:161:10: warning: unused variable 'de' [-Wunused-variable]
  161 |     bool de=0;
      |          ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3160 KB Output is correct
8 Correct 2 ms 3212 KB Output is correct
9 Correct 44 ms 26960 KB Output is correct
10 Correct 54 ms 34132 KB Output is correct
11 Correct 55 ms 32852 KB Output is correct
12 Correct 56 ms 34900 KB Output is correct
13 Correct 52 ms 37508 KB Output is correct
14 Correct 58 ms 26452 KB Output is correct
15 Correct 87 ms 38112 KB Output is correct
16 Correct 89 ms 35124 KB Output is correct
17 Correct 93 ms 41656 KB Output is correct
18 Correct 84 ms 39612 KB Output is correct
19 Incorrect 41 ms 12368 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 96 ms 31080 KB Output is correct
4 Correct 95 ms 32100 KB Output is correct
5 Correct 95 ms 31836 KB Output is correct
6 Correct 89 ms 31948 KB Output is correct
7 Correct 93 ms 32068 KB Output is correct
8 Correct 88 ms 31016 KB Output is correct
9 Correct 101 ms 31812 KB Output is correct
10 Correct 90 ms 30804 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 2 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3160 KB Output is correct
8 Correct 2 ms 3212 KB Output is correct
9 Correct 44 ms 26960 KB Output is correct
10 Correct 54 ms 34132 KB Output is correct
11 Correct 55 ms 32852 KB Output is correct
12 Correct 56 ms 34900 KB Output is correct
13 Correct 52 ms 37508 KB Output is correct
14 Correct 58 ms 26452 KB Output is correct
15 Correct 87 ms 38112 KB Output is correct
16 Correct 89 ms 35124 KB Output is correct
17 Correct 93 ms 41656 KB Output is correct
18 Correct 84 ms 39612 KB Output is correct
19 Correct 96 ms 31080 KB Output is correct
20 Correct 95 ms 32100 KB Output is correct
21 Correct 95 ms 31836 KB Output is correct
22 Correct 89 ms 31948 KB Output is correct
23 Correct 93 ms 32068 KB Output is correct
24 Correct 88 ms 31016 KB Output is correct
25 Correct 101 ms 31812 KB Output is correct
26 Correct 90 ms 30804 KB Output is correct
27 Correct 2 ms 3160 KB Output is correct
28 Correct 2 ms 3164 KB Output is correct
29 Correct 2 ms 3164 KB Output is correct
30 Correct 2 ms 3164 KB Output is correct
31 Correct 2 ms 3164 KB Output is correct
32 Incorrect 2 ms 3164 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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