oj.uz

Submission #983042

# Submission time Handle Problem Language Result Execution time Memory
983042 2024-05-15T07:17:51 Z shenfe1 Swapping Cities (APIO20_swap) C++17
100 / 100
 370 ms 84196 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 cnt[MAX];
int mn[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;
    mn[to]=min(mn[to],mn[v]);
    dfs(to,v);
  }
  tout[v]=timer;
}

void dfs1(int v,int p){
  cnt[v]=mark[v];
  for(auto to:g[v]){
    if(to==p)continue;
    dfs1(to,v);
    cnt[v]+=cnt[to];
  }
  if(cnt[v])mn[v]=cost[v];
}

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++){
    mn[i]=inf;
  }
  dfs1(D.get(1),D.get(1));
  dfs(D.get(1),D.get(1));
}

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);
  if(max(min(mn[X],mn[Y]),cost[l])==inf)return -1;
  return max(min(mn[X],mn[Y]),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 24920 KB Output is correct
2 Correct 12 ms 25180 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 13 ms 25180 KB Output is correct
6 Correct 13 ms 25180 KB Output is correct
7 Correct 12 ms 25180 KB Output is correct
8 Correct 12 ms 25176 KB Output is correct
9 Correct 93 ms 47560 KB Output is correct
10 Correct 138 ms 52420 KB Output is correct
11 Correct 125 ms 51944 KB Output is correct
12 Correct 132 ms 53704 KB Output is correct
13 Correct 104 ms 57624 KB Output is correct
14 Correct 102 ms 47764 KB Output is correct
15 Correct 210 ms 55492 KB Output is correct
16 Correct 210 ms 54480 KB Output is correct
17 Correct 211 ms 56456 KB Output is correct
18 Correct 210 ms 60292 KB Output is correct
19 Correct 77 ms 33764 KB Output is correct
20 Correct 202 ms 55572 KB Output is correct
21 Correct 193 ms 54920 KB Output is correct
22 Correct 201 ms 56980 KB Output is correct
23 Correct 205 ms 60732 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24920 KB Output is correct
2 Correct 12 ms 25180 KB Output is correct
3 Correct 212 ms 62460 KB Output is correct
4 Correct 200 ms 64144 KB Output is correct
5 Correct 196 ms 63216 KB Output is correct
6 Correct 198 ms 63556 KB Output is correct
7 Correct 204 ms 63684 KB Output is correct
8 Correct 194 ms 61984 KB Output is correct
9 Correct 215 ms 63360 KB Output is correct
10 Correct 209 ms 61872 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Correct 11 ms 24920 KB Output is correct
3 Correct 12 ms 25180 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 13 ms 25180 KB Output is correct
7 Correct 13 ms 25180 KB Output is correct
8 Correct 12 ms 25180 KB Output is correct
9 Correct 12 ms 25176 KB Output is correct
10 Correct 93 ms 47560 KB Output is correct
11 Correct 138 ms 52420 KB Output is correct
12 Correct 125 ms 51944 KB Output is correct
13 Correct 132 ms 53704 KB Output is correct
14 Correct 104 ms 57624 KB Output is correct
15 Correct 13 ms 25180 KB Output is correct
16 Correct 12 ms 25180 KB Output is correct
17 Correct 12 ms 25324 KB Output is correct
18 Correct 12 ms 25180 KB Output is correct
19 Correct 13 ms 25180 KB Output is correct
20 Correct 12 ms 25180 KB Output is correct
21 Correct 12 ms 25180 KB Output is correct
22 Correct 12 ms 25240 KB Output is correct
23 Correct 12 ms 25180 KB Output is correct
24 Correct 12 ms 25180 KB Output is correct
25 Correct 12 ms 25324 KB Output is correct
26 Correct 14 ms 25180 KB Output is correct
27 Correct 12 ms 25432 KB Output is correct
28 Correct 12 ms 25244 KB Output is correct
29 Correct 13 ms 25496 KB Output is correct
30 Correct 13 ms 25436 KB Output is correct
31 Correct 13 ms 25436 KB Output is correct
32 Correct 15 ms 25180 KB Output is correct
33 Correct 13 ms 25500 KB Output is correct
34 Correct 22 ms 28956 KB Output is correct
35 Correct 125 ms 53700 KB Output is correct
36 Correct 123 ms 53700 KB Output is correct
37 Correct 118 ms 53448 KB Output is correct
38 Correct 126 ms 53460 KB Output is correct
39 Correct 131 ms 52772 KB Output is correct
40 Correct 129 ms 50576 KB Output is correct
41 Correct 136 ms 53704 KB Output is correct
42 Correct 117 ms 53700 KB Output is correct
43 Correct 100 ms 58756 KB Output is correct
44 Correct 126 ms 53704 KB Output is correct
45 Correct 151 ms 67316 KB Output is correct
46 Correct 125 ms 53572 KB Output is correct
47 Correct 139 ms 53748 KB Output is correct
48 Correct 129 ms 58488 KB Output is correct
49 Correct 103 ms 66072 KB Output is correct
50 Correct 83 ms 56988 KB Output is correct
51 Correct 121 ms 61692 KB Output is correct
52 Correct 173 ms 69656 KB Output is correct
53 Correct 201 ms 72640 KB Output is correct
54 Correct 203 ms 79804 KB Output is correct
55 Correct 106 ms 58376 KB Output is correct
56 Correct 176 ms 74892 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24920 KB Output is correct
2 Correct 12 ms 25180 KB Output is correct
3 Correct 12 ms 24924 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 13 ms 25180 KB Output is correct
6 Correct 13 ms 25180 KB Output is correct
7 Correct 12 ms 25180 KB Output is correct
8 Correct 12 ms 25176 KB Output is correct
9 Correct 93 ms 47560 KB Output is correct
10 Correct 138 ms 52420 KB Output is correct
11 Correct 125 ms 51944 KB Output is correct
12 Correct 132 ms 53704 KB Output is correct
13 Correct 104 ms 57624 KB Output is correct
14 Correct 102 ms 47764 KB Output is correct
15 Correct 210 ms 55492 KB Output is correct
16 Correct 210 ms 54480 KB Output is correct
17 Correct 211 ms 56456 KB Output is correct
18 Correct 210 ms 60292 KB Output is correct
19 Correct 212 ms 62460 KB Output is correct
20 Correct 200 ms 64144 KB Output is correct
21 Correct 196 ms 63216 KB Output is correct
22 Correct 198 ms 63556 KB Output is correct
23 Correct 204 ms 63684 KB Output is correct
24 Correct 194 ms 61984 KB Output is correct
25 Correct 215 ms 63360 KB Output is correct
26 Correct 209 ms 61872 KB Output is correct
27 Correct 13 ms 25180 KB Output is correct
28 Correct 12 ms 25180 KB Output is correct
29 Correct 12 ms 25324 KB Output is correct
30 Correct 12 ms 25180 KB Output is correct
31 Correct 13 ms 25180 KB Output is correct
32 Correct 12 ms 25180 KB Output is correct
33 Correct 12 ms 25180 KB Output is correct
34 Correct 12 ms 25240 KB Output is correct
35 Correct 12 ms 25180 KB Output is correct
36 Correct 22 ms 28956 KB Output is correct
37 Correct 125 ms 53700 KB Output is correct
38 Correct 123 ms 53700 KB Output is correct
39 Correct 118 ms 53448 KB Output is correct
40 Correct 126 ms 53460 KB Output is correct
41 Correct 131 ms 52772 KB Output is correct
42 Correct 129 ms 50576 KB Output is correct
43 Correct 136 ms 53704 KB Output is correct
44 Correct 117 ms 53700 KB Output is correct
45 Correct 100 ms 58756 KB Output is correct
46 Correct 126 ms 53704 KB Output is correct
47 Correct 27 ms 29052 KB Output is correct
48 Correct 202 ms 56240 KB Output is correct
49 Correct 193 ms 58056 KB Output is correct
50 Correct 192 ms 58056 KB Output is correct
51 Correct 206 ms 57800 KB Output is correct
52 Correct 184 ms 56104 KB Output is correct
53 Correct 155 ms 49580 KB Output is correct
54 Correct 236 ms 58656 KB Output is correct
55 Correct 191 ms 58128 KB Output is correct
56 Correct 228 ms 62404 KB Output is correct
57 Correct 212 ms 58736 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24924 KB Output is correct
2 Correct 11 ms 24920 KB Output is correct
3 Correct 12 ms 25180 KB Output is correct
4 Correct 12 ms 24924 KB Output is correct
5 Correct 12 ms 24924 KB Output is correct
6 Correct 13 ms 25180 KB Output is correct
7 Correct 13 ms 25180 KB Output is correct
8 Correct 12 ms 25180 KB Output is correct
9 Correct 12 ms 25176 KB Output is correct
10 Correct 93 ms 47560 KB Output is correct
11 Correct 138 ms 52420 KB Output is correct
12 Correct 125 ms 51944 KB Output is correct
13 Correct 132 ms 53704 KB Output is correct
14 Correct 104 ms 57624 KB Output is correct
15 Correct 102 ms 47764 KB Output is correct
16 Correct 210 ms 55492 KB Output is correct
17 Correct 210 ms 54480 KB Output is correct
18 Correct 211 ms 56456 KB Output is correct
19 Correct 210 ms 60292 KB Output is correct
20 Correct 212 ms 62460 KB Output is correct
21 Correct 200 ms 64144 KB Output is correct
22 Correct 196 ms 63216 KB Output is correct
23 Correct 198 ms 63556 KB Output is correct
24 Correct 204 ms 63684 KB Output is correct
25 Correct 194 ms 61984 KB Output is correct
26 Correct 215 ms 63360 KB Output is correct
27 Correct 209 ms 61872 KB Output is correct
28 Correct 13 ms 25180 KB Output is correct
29 Correct 12 ms 25180 KB Output is correct
30 Correct 12 ms 25324 KB Output is correct
31 Correct 12 ms 25180 KB Output is correct
32 Correct 13 ms 25180 KB Output is correct
33 Correct 12 ms 25180 KB Output is correct
34 Correct 12 ms 25180 KB Output is correct
35 Correct 12 ms 25240 KB Output is correct
36 Correct 12 ms 25180 KB Output is correct
37 Correct 22 ms 28956 KB Output is correct
38 Correct 125 ms 53700 KB Output is correct
39 Correct 123 ms 53700 KB Output is correct
40 Correct 118 ms 53448 KB Output is correct
41 Correct 126 ms 53460 KB Output is correct
42 Correct 131 ms 52772 KB Output is correct
43 Correct 129 ms 50576 KB Output is correct
44 Correct 136 ms 53704 KB Output is correct
45 Correct 117 ms 53700 KB Output is correct
46 Correct 100 ms 58756 KB Output is correct
47 Correct 126 ms 53704 KB Output is correct
48 Correct 27 ms 29052 KB Output is correct
49 Correct 202 ms 56240 KB Output is correct
50 Correct 193 ms 58056 KB Output is correct
51 Correct 192 ms 58056 KB Output is correct
52 Correct 206 ms 57800 KB Output is correct
53 Correct 184 ms 56104 KB Output is correct
54 Correct 155 ms 49580 KB Output is correct
55 Correct 236 ms 58656 KB Output is correct
56 Correct 191 ms 58128 KB Output is correct
57 Correct 228 ms 62404 KB Output is correct
58 Correct 212 ms 58736 KB Output is correct
59 Correct 77 ms 33764 KB Output is correct
60 Correct 202 ms 55572 KB Output is correct
61 Correct 193 ms 54920 KB Output is correct
62 Correct 201 ms 56980 KB Output is correct
63 Correct 205 ms 60732 KB Output is correct
64 Correct 12 ms 25180 KB Output is correct
65 Correct 12 ms 25324 KB Output is correct
66 Correct 14 ms 25180 KB Output is correct
67 Correct 12 ms 25432 KB Output is correct
68 Correct 12 ms 25244 KB Output is correct
69 Correct 13 ms 25496 KB Output is correct
70 Correct 13 ms 25436 KB Output is correct
71 Correct 13 ms 25436 KB Output is correct
72 Correct 15 ms 25180 KB Output is correct
73 Correct 13 ms 25500 KB Output is correct
74 Correct 151 ms 67316 KB Output is correct
75 Correct 125 ms 53572 KB Output is correct
76 Correct 139 ms 53748 KB Output is correct
77 Correct 129 ms 58488 KB Output is correct
78 Correct 103 ms 66072 KB Output is correct
79 Correct 83 ms 56988 KB Output is correct
80 Correct 121 ms 61692 KB Output is correct
81 Correct 173 ms 69656 KB Output is correct
82 Correct 201 ms 72640 KB Output is correct
83 Correct 203 ms 79804 KB Output is correct
84 Correct 106 ms 58376 KB Output is correct
85 Correct 176 ms 74892 KB Output is correct
86 Correct 85 ms 39856 KB Output is correct
87 Correct 220 ms 56956 KB Output is correct
88 Correct 212 ms 57032 KB Output is correct
89 Correct 278 ms 60488 KB Output is correct
90 Correct 193 ms 72164 KB Output is correct
91 Correct 212 ms 69832 KB Output is correct
92 Correct 286 ms 63884 KB Output is correct
93 Correct 322 ms 73256 KB Output is correct
94 Correct 370 ms 77064 KB Output is correct
95 Correct 306 ms 84196 KB Output is correct
96 Correct 238 ms 61332 KB Output is correct
97 Correct 321 ms 68912 KB Output is correct