oj.uz

Submission #1088333

# Submission time Handle Problem Language Result Execution time Memory
1088333 2024-09-14T09:02:58 Z modwwe Swapping Cities (APIO20_swap) C++17
0 / 100
 92 ms 33144 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];
int st[17][100001];
int st2[17][100001];
int depth[100001];
vector<ib> v[100001];
void dfs(int x,int y)
{
    st[0][x]=y;
    depth[x]=depth[y]+1;
    for(auto f:v[x])
        if(f.a!=y)
        {
            st2[0][f.a]=f.b,dfs(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;
    for(int j=0; j<17; ++j)
        if(bit(ss,j))
            s=max(s,st2[j][x]), x=st[j][x];
    if(x==y) return s;
    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]);
    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 if(!de)de=1,s5=a[i].c;

    }
    dfs(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)
{
        l++;
        r++;
        if(s5==inf) return -1;
        else  return (s5,lca(l,r));
}

Compilation message

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:158:23: warning: left operand of comma operator has no effect [-Wunused-value]
  158 |         else  return (s5,lca(l,r));
      |                       ^~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 2904 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 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 47 ms 22584 KB Output is correct
10 Correct 56 ms 27408 KB Output is correct
11 Correct 55 ms 26964 KB Output is correct
12 Correct 63 ms 28244 KB Output is correct
13 Correct 62 ms 29036 KB Output is correct
14 Correct 46 ms 22512 KB Output is correct
15 Correct 92 ms 31712 KB Output is correct
16 Correct 80 ms 30464 KB Output is correct
17 Correct 84 ms 33144 KB Output is correct
18 Correct 77 ms 32444 KB Output is correct
19 Incorrect 63 ms 12160 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 2904 KB Output is correct
3 Incorrect 67 ms 29008 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3160 KB Output is correct
2 Correct 2 ms 2904 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 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Incorrect 1 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 1 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 3160 KB Output is correct
2 Correct 2 ms 2904 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 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 47 ms 22584 KB Output is correct
10 Correct 56 ms 27408 KB Output is correct
11 Correct 55 ms 26964 KB Output is correct
12 Correct 63 ms 28244 KB Output is correct
13 Correct 62 ms 29036 KB Output is correct
14 Correct 46 ms 22512 KB Output is correct
15 Correct 92 ms 31712 KB Output is correct
16 Correct 80 ms 30464 KB Output is correct
17 Correct 84 ms 33144 KB Output is correct
18 Correct 77 ms 32444 KB Output is correct
19 Incorrect 67 ms 29008 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

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