oj.uz

Submission #1088573

# Submission time Handle Problem Language Result Execution time Memory
1088573 2024-09-14T15:40:54 Z modwwe Swapping Cities (APIO20_swap) C++17
100 / 100
 209 ms 41856 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;
    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,dp[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 dp[a[i].a]=min(dp[a[i].a],a[i].c),dp[a[i].b]=min(dp[a[i].b],a[i].c);
        //,cout<<a[i].a<<" "<<a[i].b,down

    }
    dfs(1,0);
    dfs2(1,0);

    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&&m==n-1) 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:171:10: warning: unused variable 'de' [-Wunused-variable]
  171 |     bool de=0;
      |          ^~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 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 3160 KB Output is correct
7 Correct 2 ms 3060 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 48 ms 27228 KB Output is correct
10 Correct 63 ms 34552 KB Output is correct
11 Correct 59 ms 33364 KB Output is correct
12 Correct 68 ms 35412 KB Output is correct
13 Correct 58 ms 37992 KB Output is correct
14 Correct 54 ms 26708 KB Output is correct
15 Correct 90 ms 38364 KB Output is correct
16 Correct 95 ms 35452 KB Output is correct
17 Correct 99 ms 41856 KB Output is correct
18 Correct 97 ms 39912 KB Output is correct
19 Correct 53 ms 13536 KB Output is correct
20 Correct 157 ms 38592 KB Output is correct
21 Correct 171 ms 36724 KB Output is correct
22 Correct 158 ms 40152 KB Output is correct
23 Correct 143 ms 41144 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 83 ms 31596 KB Output is correct
4 Correct 91 ms 32556 KB Output is correct
5 Correct 97 ms 32096 KB Output is correct
6 Correct 88 ms 32300 KB Output is correct
7 Correct 97 ms 32324 KB Output is correct
8 Correct 88 ms 31348 KB Output is correct
9 Correct 99 ms 32048 KB Output is correct
10 Correct 94 ms 31108 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 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 3160 KB Output is correct
7 Correct 2 ms 3060 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 2 ms 3072 KB Output is correct
11 Correct 3 ms 3164 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 2 ms 3164 KB Output is correct
14 Correct 2 ms 3160 KB Output is correct
15 Correct 2 ms 3164 KB Output is correct
16 Correct 2 ms 3164 KB Output is correct
17 Correct 2 ms 3160 KB Output is correct
18 Correct 2 ms 3144 KB Output is correct
19 Correct 2 ms 2908 KB Output is correct
20 Correct 2 ms 3164 KB Output is correct
21 Correct 2 ms 3092 KB Output is correct
22 Correct 2 ms 3068 KB Output is correct
23 Correct 2 ms 3160 KB Output is correct
24 Correct 2 ms 3164 KB Output is correct
25 Correct 2 ms 3164 KB Output is correct
26 Correct 2 ms 3164 KB Output is correct
27 Correct 2 ms 3164 KB Output is correct
28 Correct 3 ms 3164 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 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 3060 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 48 ms 27228 KB Output is correct
11 Correct 63 ms 34552 KB Output is correct
12 Correct 59 ms 33364 KB Output is correct
13 Correct 68 ms 35412 KB Output is correct
14 Correct 58 ms 37992 KB Output is correct
15 Correct 2 ms 3072 KB Output is correct
16 Correct 3 ms 3164 KB Output is correct
17 Correct 2 ms 3164 KB Output is correct
18 Correct 2 ms 3164 KB Output is correct
19 Correct 2 ms 3160 KB Output is correct
20 Correct 2 ms 3164 KB Output is correct
21 Correct 2 ms 3164 KB Output is correct
22 Correct 2 ms 3160 KB Output is correct
23 Correct 2 ms 3144 KB Output is correct
24 Correct 2 ms 2908 KB Output is correct
25 Correct 2 ms 3164 KB Output is correct
26 Correct 2 ms 3092 KB Output is correct
27 Correct 2 ms 3068 KB Output is correct
28 Correct 2 ms 3160 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 Correct 2 ms 3164 KB Output is correct
33 Correct 3 ms 3164 KB Output is correct
34 Correct 9 ms 6236 KB Output is correct
35 Correct 66 ms 34384 KB Output is correct
36 Correct 65 ms 30804 KB Output is correct
37 Correct 60 ms 28152 KB Output is correct
38 Correct 61 ms 27244 KB Output is correct
39 Correct 60 ms 26644 KB Output is correct
40 Correct 52 ms 24892 KB Output is correct
41 Correct 65 ms 32084 KB Output is correct
42 Correct 61 ms 33364 KB Output is correct
43 Correct 65 ms 35164 KB Output is correct
44 Correct 57 ms 27676 KB Output is correct
45 Correct 62 ms 26380 KB Output is correct
46 Correct 64 ms 29268 KB Output is correct
47 Correct 57 ms 26960 KB Output is correct
48 Correct 56 ms 27428 KB Output is correct
49 Correct 39 ms 11344 KB Output is correct
50 Correct 32 ms 10728 KB Output is correct
51 Correct 52 ms 22336 KB Output is correct
52 Correct 75 ms 32924 KB Output is correct
53 Correct 77 ms 32528 KB Output is correct
54 Correct 101 ms 37524 KB Output is correct
55 Correct 58 ms 36948 KB Output is correct
56 Correct 79 ms 31568 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2904 KB Output is correct
2 Correct 1 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 3160 KB Output is correct
7 Correct 2 ms 3060 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 48 ms 27228 KB Output is correct
10 Correct 63 ms 34552 KB Output is correct
11 Correct 59 ms 33364 KB Output is correct
12 Correct 68 ms 35412 KB Output is correct
13 Correct 58 ms 37992 KB Output is correct
14 Correct 54 ms 26708 KB Output is correct
15 Correct 90 ms 38364 KB Output is correct
16 Correct 95 ms 35452 KB Output is correct
17 Correct 99 ms 41856 KB Output is correct
18 Correct 97 ms 39912 KB Output is correct
19 Correct 83 ms 31596 KB Output is correct
20 Correct 91 ms 32556 KB Output is correct
21 Correct 97 ms 32096 KB Output is correct
22 Correct 88 ms 32300 KB Output is correct
23 Correct 97 ms 32324 KB Output is correct
24 Correct 88 ms 31348 KB Output is correct
25 Correct 99 ms 32048 KB Output is correct
26 Correct 94 ms 31108 KB Output is correct
27 Correct 2 ms 3072 KB Output is correct
28 Correct 3 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 3160 KB Output is correct
32 Correct 2 ms 3164 KB Output is correct
33 Correct 2 ms 3164 KB Output is correct
34 Correct 2 ms 3160 KB Output is correct
35 Correct 2 ms 3144 KB Output is correct
36 Correct 9 ms 6236 KB Output is correct
37 Correct 66 ms 34384 KB Output is correct
38 Correct 65 ms 30804 KB Output is correct
39 Correct 60 ms 28152 KB Output is correct
40 Correct 61 ms 27244 KB Output is correct
41 Correct 60 ms 26644 KB Output is correct
42 Correct 52 ms 24892 KB Output is correct
43 Correct 65 ms 32084 KB Output is correct
44 Correct 61 ms 33364 KB Output is correct
45 Correct 65 ms 35164 KB Output is correct
46 Correct 57 ms 27676 KB Output is correct
47 Correct 14 ms 6596 KB Output is correct
48 Correct 171 ms 36576 KB Output is correct
49 Correct 180 ms 34524 KB Output is correct
50 Correct 182 ms 33120 KB Output is correct
51 Correct 176 ms 32452 KB Output is correct
52 Correct 149 ms 30424 KB Output is correct
53 Correct 119 ms 25160 KB Output is correct
54 Correct 177 ms 36536 KB Output is correct
55 Correct 162 ms 37468 KB Output is correct
56 Correct 137 ms 40892 KB Output is correct
57 Correct 147 ms 33084 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 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 3060 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 48 ms 27228 KB Output is correct
11 Correct 63 ms 34552 KB Output is correct
12 Correct 59 ms 33364 KB Output is correct
13 Correct 68 ms 35412 KB Output is correct
14 Correct 58 ms 37992 KB Output is correct
15 Correct 54 ms 26708 KB Output is correct
16 Correct 90 ms 38364 KB Output is correct
17 Correct 95 ms 35452 KB Output is correct
18 Correct 99 ms 41856 KB Output is correct
19 Correct 97 ms 39912 KB Output is correct
20 Correct 83 ms 31596 KB Output is correct
21 Correct 91 ms 32556 KB Output is correct
22 Correct 97 ms 32096 KB Output is correct
23 Correct 88 ms 32300 KB Output is correct
24 Correct 97 ms 32324 KB Output is correct
25 Correct 88 ms 31348 KB Output is correct
26 Correct 99 ms 32048 KB Output is correct
27 Correct 94 ms 31108 KB Output is correct
28 Correct 2 ms 3072 KB Output is correct
29 Correct 3 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 Correct 2 ms 3160 KB Output is correct
33 Correct 2 ms 3164 KB Output is correct
34 Correct 2 ms 3164 KB Output is correct
35 Correct 2 ms 3160 KB Output is correct
36 Correct 2 ms 3144 KB Output is correct
37 Correct 9 ms 6236 KB Output is correct
38 Correct 66 ms 34384 KB Output is correct
39 Correct 65 ms 30804 KB Output is correct
40 Correct 60 ms 28152 KB Output is correct
41 Correct 61 ms 27244 KB Output is correct
42 Correct 60 ms 26644 KB Output is correct
43 Correct 52 ms 24892 KB Output is correct
44 Correct 65 ms 32084 KB Output is correct
45 Correct 61 ms 33364 KB Output is correct
46 Correct 65 ms 35164 KB Output is correct
47 Correct 57 ms 27676 KB Output is correct
48 Correct 14 ms 6596 KB Output is correct
49 Correct 171 ms 36576 KB Output is correct
50 Correct 180 ms 34524 KB Output is correct
51 Correct 182 ms 33120 KB Output is correct
52 Correct 176 ms 32452 KB Output is correct
53 Correct 149 ms 30424 KB Output is correct
54 Correct 119 ms 25160 KB Output is correct
55 Correct 177 ms 36536 KB Output is correct
56 Correct 162 ms 37468 KB Output is correct
57 Correct 137 ms 40892 KB Output is correct
58 Correct 147 ms 33084 KB Output is correct
59 Correct 53 ms 13536 KB Output is correct
60 Correct 157 ms 38592 KB Output is correct
61 Correct 171 ms 36724 KB Output is correct
62 Correct 158 ms 40152 KB Output is correct
63 Correct 143 ms 41144 KB Output is correct
64 Correct 2 ms 2908 KB Output is correct
65 Correct 2 ms 3164 KB Output is correct
66 Correct 2 ms 3092 KB Output is correct
67 Correct 2 ms 3068 KB Output is correct
68 Correct 2 ms 3160 KB Output is correct
69 Correct 2 ms 3164 KB Output is correct
70 Correct 2 ms 3164 KB Output is correct
71 Correct 2 ms 3164 KB Output is correct
72 Correct 2 ms 3164 KB Output is correct
73 Correct 3 ms 3164 KB Output is correct
74 Correct 62 ms 26380 KB Output is correct
75 Correct 64 ms 29268 KB Output is correct
76 Correct 57 ms 26960 KB Output is correct
77 Correct 56 ms 27428 KB Output is correct
78 Correct 39 ms 11344 KB Output is correct
79 Correct 32 ms 10728 KB Output is correct
80 Correct 52 ms 22336 KB Output is correct
81 Correct 75 ms 32924 KB Output is correct
82 Correct 77 ms 32528 KB Output is correct
83 Correct 101 ms 37524 KB Output is correct
84 Correct 58 ms 36948 KB Output is correct
85 Correct 79 ms 31568 KB Output is correct
86 Correct 41 ms 12696 KB Output is correct
87 Correct 209 ms 33976 KB Output is correct
88 Correct 183 ms 34116 KB Output is correct
89 Correct 127 ms 30600 KB Output is correct
90 Correct 105 ms 15856 KB Output is correct
91 Correct 104 ms 17616 KB Output is correct
92 Correct 125 ms 27232 KB Output is correct
93 Correct 195 ms 38408 KB Output is correct
94 Correct 161 ms 36920 KB Output is correct
95 Correct 199 ms 41044 KB Output is correct
96 Correct 155 ms 38112 KB Output is correct
97 Correct 150 ms 34780 KB Output is correct