oj.uz

Submission #983035

# Submission time Handle Problem Language Result Execution time Memory
983035 2024-05-15T07:13:49 Z shenfe1 Swapping Cities (APIO20_swap) C++17
50 / 100
 237 ms 77292 KB 
#include "swap.h"
#include <bits/stdc++.h>
 
#pragma optimize("Ofast")
#pragma target("avx2")
 
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert

const int MAX=1e6+15;
const int B=300;
const int N=104;
const int block=400;
const int maxB=MAX/B+10;
const ll inf=2e9;  
const int mod=998244353;
const int mod1=1e9+9;
const ld eps=1e-9;
 
int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};
 
int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
int mark[MAX];
int cost[MAX];
vector<int> g[MAX];

struct DSU{
  int f[MAX];
  int cur;

  void init(int n,int ver){
    cur=ver;
    for(int i=1;i<=n;i++)f[i]=i;
  }

  int get(int v){
    return (f[v]==v?v:f[v]=get(f[v]));
  }

  void unite(int a,int b,bool is,int C){
    a=get(a);
    b=get(b);
    int x=++cur;
    g[x].pb(a);
    g[x].pb(b);
    // cout<<x<<" "<<a<<"\n";
    // cout<<x<<" "<<b<<"\n";
    mark[x]=is;
    cost[x]=C;
    f[a]=f[b]=x;
  }

  void cycle(int a,int C){
    a=get(a);
    int x=++cur;
    cost[x]=C;
    g[x].pb(a);
    // cout<<x<<" "<<a<<"\n";
    mark[x]=1;
    f[a]=x;
  }
}D;

int up[MAX][20];
int tin[MAX],tout[MAX],timer;
int mn[MAX];
int pr[MAX];
int deg[MAX];

void dfs(int v,int p){
  tin[v]=++timer;
  up[v][0]=p;
  // cout<<v<<" "<<p<<"\n";
  for(int i=1;i<20;i++)up[v][i]=up[up[v][i-1]][i-1];
  for(auto to:g[v]){
    if(to==p)continue;
    pr[to]=min(pr[to],pr[v]);
    dfs(to,v);
  }
  tout[v]=timer;
}

void dfs1(int v,int p){
  for(auto to:g[v]){
    if(to==p)continue;
    dfs1(to,v);
    // cout<<v<<" -> "<<to<<"\n";
    mn[v]=min(mn[v],mn[to]);
  }
}

void init(int N, int M,vector<int> U,vector<int> V,vector<int> W) {
  D.init(N+M,N);
  vector<pair<int,pii>> e;
  for(int i=0;i<M;i++){
    U[i]++;V[i]++;
    e.pb({W[i],{U[i],V[i]}});
  }
  sort(all(e));
  for(auto x:e){
    int w=x.F;
    int u=x.S.F;
    int v=x.S.S;
    // cerr<<w<<" "<<u<<" "<<v<<"\n";
    if(D.get(u)!=D.get(v)){
      deg[u]++;
      deg[v]++;
      bool is=(deg[u]==3||deg[v]==3);
      D.unite(u,v,is,w);
      // cout<<u<<" "<<v<<" "<<D.get(u)<<" "<<D.get(v)<<"\n";
    }
    else{
      D.cycle(u,w);
      // cout<<D.cur<<" "<<w<<"\n";
    }
  }
  // cerr<<1<<"\n";
  for(int i=1;i<=D.cur;i++){
    if(!mark[i])mn[i]=pr[i]=inf;
    else mn[i]=pr[i]=cost[i];
  }
  // cout<<D.get(1)<<"\n";
  dfs1(D.get(1),D.get(1));
  dfs(D.get(1),D.get(1));
  // for(int i=1;i<=D.cur;i++)cout<<i-1<<" "<<mn[i]<<" "<<mark[i]<<" "<<cost[i]<<"\n";
}

int par(int a,int b){
  return (tin[a]<=tin[b]&&tout[b]<=tout[a]);
}

int lca(int a,int b){
  if(par(a,b))return a;
  if(par(b,a))return b;
  for(int i=19;i>=0;i--){
    if(!par(up[a][i],b)){
      a=up[a][i];
    }
  }
  return up[a][0];
}

int getMinimumFuelCapacity(int X, int Y) {
  X++;
  Y++;
  int l=lca(X,Y);
  // cout<<mn[X]<<" "<<mn[Y]<<" "<<cost[lca(X,Y)]<<"\n";
  if(max(min(mn[l],pr[l]),cost[l])==inf)return -1;
  return max(min(mn[l],pr[l]),cost[l]);
}

Compilation message

swap.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize("Ofast")
      | 
swap.cpp:5: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    5 | #pragma target("avx2")
      |

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Correct 11 ms 24892 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 11 ms 24924 KB Output is correct
5 Correct 12 ms 25180 KB Output is correct
6 Correct 12 ms 25120 KB Output is correct
7 Correct 12 ms 25432 KB Output is correct
8 Correct 12 ms 25180 KB Output is correct
9 Correct 88 ms 46536 KB Output is correct
10 Correct 125 ms 51152 KB Output is correct
11 Correct 115 ms 50780 KB Output is correct
12 Correct 123 ms 52420 KB Output is correct
13 Correct 99 ms 56264 KB Output is correct
14 Correct 104 ms 46536 KB Output is correct
15 Correct 200 ms 53120 KB Output is correct
16 Correct 184 ms 52168 KB Output is correct
17 Correct 208 ms 53940 KB Output is correct
18 Correct 204 ms 57776 KB Output is correct
19 Correct 76 ms 32584 KB Output is correct
20 Correct 220 ms 53444 KB Output is correct
21 Correct 181 ms 52484 KB Output is correct
22 Correct 211 ms 54228 KB Output is correct
23 Correct 229 ms 58144 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Correct 11 ms 24892 KB Output is correct
3 Correct 216 ms 60172 KB Output is correct
4 Correct 195 ms 61828 KB Output is correct
5 Correct 195 ms 60772 KB Output is correct
6 Correct 209 ms 61664 KB Output is correct
7 Correct 213 ms 61556 KB Output is correct
8 Correct 190 ms 59888 KB Output is correct
9 Correct 209 ms 61124 KB Output is correct
10 Correct 214 ms 59704 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Correct 11 ms 24892 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 11 ms 24924 KB Output is correct
5 Correct 12 ms 25180 KB Output is correct
6 Correct 12 ms 25120 KB Output is correct
7 Correct 12 ms 25432 KB Output is correct
8 Correct 12 ms 25180 KB Output is correct
9 Correct 13 ms 24920 KB Output is correct
10 Correct 11 ms 25180 KB Output is correct
11 Correct 12 ms 25284 KB Output is correct
12 Correct 12 ms 25176 KB Output is correct
13 Correct 12 ms 25180 KB Output is correct
14 Correct 11 ms 25072 KB Output is correct
15 Correct 12 ms 25180 KB Output is correct
16 Correct 12 ms 25300 KB Output is correct
17 Correct 11 ms 25180 KB Output is correct
18 Correct 14 ms 25180 KB Output is correct
19 Correct 12 ms 25180 KB Output is correct
20 Correct 13 ms 25180 KB Output is correct
21 Correct 12 ms 25176 KB Output is correct
22 Correct 12 ms 25436 KB Output is correct
23 Correct 11 ms 25180 KB Output is correct
24 Correct 13 ms 25436 KB Output is correct
25 Correct 13 ms 25436 KB Output is correct
26 Correct 13 ms 25436 KB Output is correct
27 Correct 12 ms 25180 KB Output is correct
28 Correct 13 ms 25432 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24920 KB Output is correct
2 Correct 11 ms 24924 KB Output is correct
3 Correct 11 ms 24892 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 12 ms 25180 KB Output is correct
7 Correct 12 ms 25120 KB Output is correct
8 Correct 12 ms 25432 KB Output is correct
9 Correct 12 ms 25180 KB Output is correct
10 Correct 88 ms 46536 KB Output is correct
11 Correct 125 ms 51152 KB Output is correct
12 Correct 115 ms 50780 KB Output is correct
13 Correct 123 ms 52420 KB Output is correct
14 Correct 99 ms 56264 KB Output is correct
15 Correct 11 ms 25180 KB Output is correct
16 Correct 12 ms 25284 KB Output is correct
17 Correct 12 ms 25176 KB Output is correct
18 Correct 12 ms 25180 KB Output is correct
19 Correct 11 ms 25072 KB Output is correct
20 Correct 12 ms 25180 KB Output is correct
21 Correct 12 ms 25300 KB Output is correct
22 Correct 11 ms 25180 KB Output is correct
23 Correct 14 ms 25180 KB Output is correct
24 Correct 12 ms 25180 KB Output is correct
25 Correct 13 ms 25180 KB Output is correct
26 Correct 12 ms 25176 KB Output is correct
27 Correct 12 ms 25436 KB Output is correct
28 Correct 11 ms 25180 KB Output is correct
29 Correct 13 ms 25436 KB Output is correct
30 Correct 13 ms 25436 KB Output is correct
31 Correct 13 ms 25436 KB Output is correct
32 Correct 12 ms 25180 KB Output is correct
33 Correct 13 ms 25432 KB Output is correct
34 Correct 22 ms 28700 KB Output is correct
35 Correct 119 ms 52384 KB Output is correct
36 Correct 133 ms 52216 KB Output is correct
37 Correct 118 ms 52168 KB Output is correct
38 Correct 121 ms 51904 KB Output is correct
39 Correct 118 ms 51908 KB Output is correct
40 Correct 123 ms 49604 KB Output is correct
41 Correct 122 ms 52284 KB Output is correct
42 Correct 118 ms 52212 KB Output is correct
43 Correct 100 ms 57540 KB Output is correct
44 Correct 124 ms 52420 KB Output is correct
45 Correct 190 ms 65480 KB Output is correct
46 Correct 120 ms 52352 KB Output is correct
47 Correct 133 ms 52420 KB Output is correct
48 Correct 135 ms 56868 KB Output is correct
49 Correct 115 ms 64588 KB Output is correct
50 Correct 84 ms 55460 KB Output is correct
51 Correct 130 ms 60104 KB Output is correct
52 Correct 172 ms 67796 KB Output is correct
53 Correct 195 ms 70332 KB Output is correct
54 Correct 205 ms 77292 KB Output is correct
55 Correct 99 ms 57032 KB Output is correct
56 Correct 174 ms 72640 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Correct 11 ms 24892 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 11 ms 24924 KB Output is correct
5 Correct 12 ms 25180 KB Output is correct
6 Correct 12 ms 25120 KB Output is correct
7 Correct 12 ms 25432 KB Output is correct
8 Correct 12 ms 25180 KB Output is correct
9 Correct 88 ms 46536 KB Output is correct
10 Correct 125 ms 51152 KB Output is correct
11 Correct 115 ms 50780 KB Output is correct
12 Correct 123 ms 52420 KB Output is correct
13 Correct 99 ms 56264 KB Output is correct
14 Correct 104 ms 46536 KB Output is correct
15 Correct 200 ms 53120 KB Output is correct
16 Correct 184 ms 52168 KB Output is correct
17 Correct 208 ms 53940 KB Output is correct
18 Correct 204 ms 57776 KB Output is correct
19 Correct 216 ms 60172 KB Output is correct
20 Correct 195 ms 61828 KB Output is correct
21 Correct 195 ms 60772 KB Output is correct
22 Correct 209 ms 61664 KB Output is correct
23 Correct 213 ms 61556 KB Output is correct
24 Correct 190 ms 59888 KB Output is correct
25 Correct 209 ms 61124 KB Output is correct
26 Correct 214 ms 59704 KB Output is correct
27 Correct 11 ms 25180 KB Output is correct
28 Correct 12 ms 25284 KB Output is correct
29 Correct 12 ms 25176 KB Output is correct
30 Correct 12 ms 25180 KB Output is correct
31 Correct 11 ms 25072 KB Output is correct
32 Correct 12 ms 25180 KB Output is correct
33 Correct 12 ms 25300 KB Output is correct
34 Correct 11 ms 25180 KB Output is correct
35 Correct 14 ms 25180 KB Output is correct
36 Correct 22 ms 28700 KB Output is correct
37 Correct 119 ms 52384 KB Output is correct
38 Correct 133 ms 52216 KB Output is correct
39 Correct 118 ms 52168 KB Output is correct
40 Correct 121 ms 51904 KB Output is correct
41 Correct 118 ms 51908 KB Output is correct
42 Correct 123 ms 49604 KB Output is correct
43 Correct 122 ms 52284 KB Output is correct
44 Correct 118 ms 52212 KB Output is correct
45 Correct 100 ms 57540 KB Output is correct
46 Correct 124 ms 52420 KB Output is correct
47 Correct 27 ms 28552 KB Output is correct
48 Incorrect 237 ms 53952 KB Output isn't correct
49 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 24920 KB Output is correct
2 Correct 11 ms 24924 KB Output is correct
3 Correct 11 ms 24892 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 11 ms 24924 KB Output is correct
6 Correct 12 ms 25180 KB Output is correct
7 Correct 12 ms 25120 KB Output is correct
8 Correct 12 ms 25432 KB Output is correct
9 Correct 12 ms 25180 KB Output is correct
10 Correct 88 ms 46536 KB Output is correct
11 Correct 125 ms 51152 KB Output is correct
12 Correct 115 ms 50780 KB Output is correct
13 Correct 123 ms 52420 KB Output is correct
14 Correct 99 ms 56264 KB Output is correct
15 Correct 104 ms 46536 KB Output is correct
16 Correct 200 ms 53120 KB Output is correct
17 Correct 184 ms 52168 KB Output is correct
18 Correct 208 ms 53940 KB Output is correct
19 Correct 204 ms 57776 KB Output is correct
20 Correct 216 ms 60172 KB Output is correct
21 Correct 195 ms 61828 KB Output is correct
22 Correct 195 ms 60772 KB Output is correct
23 Correct 209 ms 61664 KB Output is correct
24 Correct 213 ms 61556 KB Output is correct
25 Correct 190 ms 59888 KB Output is correct
26 Correct 209 ms 61124 KB Output is correct
27 Correct 214 ms 59704 KB Output is correct
28 Correct 11 ms 25180 KB Output is correct
29 Correct 12 ms 25284 KB Output is correct
30 Correct 12 ms 25176 KB Output is correct
31 Correct 12 ms 25180 KB Output is correct
32 Correct 11 ms 25072 KB Output is correct
33 Correct 12 ms 25180 KB Output is correct
34 Correct 12 ms 25300 KB Output is correct
35 Correct 11 ms 25180 KB Output is correct
36 Correct 14 ms 25180 KB Output is correct
37 Correct 22 ms 28700 KB Output is correct
38 Correct 119 ms 52384 KB Output is correct
39 Correct 133 ms 52216 KB Output is correct
40 Correct 118 ms 52168 KB Output is correct
41 Correct 121 ms 51904 KB Output is correct
42 Correct 118 ms 51908 KB Output is correct
43 Correct 123 ms 49604 KB Output is correct
44 Correct 122 ms 52284 KB Output is correct
45 Correct 118 ms 52212 KB Output is correct
46 Correct 100 ms 57540 KB Output is correct
47 Correct 124 ms 52420 KB Output is correct
48 Correct 27 ms 28552 KB Output is correct
49 Incorrect 237 ms 53952 KB Output isn't correct
50 Halted 0 ms 0 KB -