oj.uz

Submission #1088551

# Submission time Handle Problem Language Result Execution time Memory
1088551 2024-09-14T15:21:22 Z modwwe Swapping Cities (APIO20_swap) C++17
30 / 100
 184 ms 41916 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 dp2[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]);
        }
    }
}
void dfs2(int x,int y)
 { int s=inf;
      for(auto f:v[x])
         if(f.a!=y)
      s=min(s,max(f.b,dp[f.a]));
      s=min(s,dp2[x]);
       for(auto f:v[x])
        if(f.a!=y)
        dp[f.a]=min(dp[f.a],max(s,f.b)),dp2[f.a]=min(dp2[f.a],max(s,f.b)),dfs2(f.a,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),dp2[i]=inf;
    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);
    dfs2(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:172:10: warning: unused variable 'de' [-Wunused-variable]
  172 |     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 2904 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 3 ms 3164 KB Output is correct
6 Correct 2 ms 3068 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 51 ms 27132 KB Output is correct
10 Correct 68 ms 34440 KB Output is correct
11 Correct 63 ms 33336 KB Output is correct
12 Correct 69 ms 35408 KB Output is correct
13 Correct 63 ms 37764 KB Output is correct
14 Correct 51 ms 26736 KB Output is correct
15 Correct 116 ms 38504 KB Output is correct
16 Correct 95 ms 35328 KB Output is correct
17 Correct 126 ms 41916 KB Output is correct
18 Correct 109 ms 40124 KB Output is correct
19 Incorrect 42 ms 12276 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 90 ms 31596 KB Output is correct
4 Correct 85 ms 32464 KB Output is correct
5 Correct 88 ms 32172 KB Output is correct
6 Correct 85 ms 32304 KB Output is correct
7 Correct 87 ms 32328 KB Output is correct
8 Correct 83 ms 31352 KB Output is correct
9 Correct 91 ms 32228 KB Output is correct
10 Correct 86 ms 31104 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 2904 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 3 ms 3164 KB Output is correct
6 Correct 2 ms 3068 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 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
23.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 2904 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct
5 Correct 3 ms 3164 KB Output is correct
6 Correct 2 ms 3068 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 51 ms 27132 KB Output is correct
10 Correct 68 ms 34440 KB Output is correct
11 Correct 63 ms 33336 KB Output is correct
12 Correct 69 ms 35408 KB Output is correct
13 Correct 63 ms 37764 KB Output is correct
14 Correct 51 ms 26736 KB Output is correct
15 Correct 116 ms 38504 KB Output is correct
16 Correct 95 ms 35328 KB Output is correct
17 Correct 126 ms 41916 KB Output is correct
18 Correct 109 ms 40124 KB Output is correct
19 Correct 90 ms 31596 KB Output is correct
20 Correct 85 ms 32464 KB Output is correct
21 Correct 88 ms 32172 KB Output is correct
22 Correct 85 ms 32304 KB Output is correct
23 Correct 87 ms 32328 KB Output is correct
24 Correct 83 ms 31352 KB Output is correct
25 Correct 91 ms 32228 KB Output is correct
26 Correct 86 ms 31104 KB Output is correct
27 Correct 2 ms 3164 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 2996 KB Output is correct
31 Correct 2 ms 3164 KB Output is correct
32 Correct 2 ms 3160 KB Output is correct
33 Correct 2 ms 3164 KB Output is correct
34 Correct 3 ms 3068 KB Output is correct
35 Correct 3 ms 3164 KB Output is correct
36 Correct 8 ms 6236 KB Output is correct
37 Correct 64 ms 34388 KB Output is correct
38 Correct 62 ms 30772 KB Output is correct
39 Correct 62 ms 28220 KB Output is correct
40 Correct 60 ms 27424 KB Output is correct
41 Correct 58 ms 26708 KB Output is correct
42 Correct 55 ms 24828 KB Output is correct
43 Correct 61 ms 32084 KB Output is correct
44 Correct 67 ms 33532 KB Output is correct
45 Correct 59 ms 35120 KB Output is correct
46 Correct 61 ms 27732 KB Output is correct
47 Correct 15 ms 6492 KB Output is correct
48 Correct 171 ms 36796 KB Output is correct
49 Correct 184 ms 34496 KB Output is correct
50 Correct 174 ms 32980 KB Output is correct
51 Correct 167 ms 32476 KB Output is correct
52 Correct 155 ms 30460 KB Output is correct
53 Correct 116 ms 25124 KB Output is correct
54 Correct 180 ms 36536 KB Output is correct
55 Correct 170 ms 37304 KB Output is correct
56 Correct 128 ms 41008 KB Output is correct
57 Correct 144 ms 33148 KB Output is correct

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 -