oj.uz

Submission #983028

# Submission time Handle Problem Language Result Execution time Memory
983028 2024-05-15T07:10:03 Z shenfe1 Swapping Cities (APIO20_swap) C++17
13 / 100
 230 ms 61292 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 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];
  // cout<<v<<" "<<mn[v]<<"\n";
  if(mark[v])mn[v]=min(mn[v],cost[v]);
  for(auto to:g[v]){
    if(to==p)continue;
    mn[to]=min(mn[to],mn[v]);
    // cout<<v<<" -> "<<to<<"\n";
    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]=inf;
    else mn[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++;
  // cout<<mn[X]<<" "<<mn[Y]<<" "<<cost[lca(X,Y)]<<"\n";
  if(max(min(mn[X],mn[Y]),cost[lca(X,Y)])==inf)return -1;
  return max(min(mn[X],mn[Y]),cost[lca(X,Y)]);
}

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 24988 KB Output is correct
2 Correct 11 ms 25180 KB Output is correct
3 Correct 11 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 12 ms 25372 KB Output is correct
6 Correct 12 ms 25436 KB Output is correct
7 Correct 12 ms 25436 KB Output is correct
8 Correct 13 ms 25436 KB Output is correct
9 Correct 95 ms 45932 KB Output is correct
10 Correct 127 ms 50540 KB Output is correct
11 Correct 126 ms 50268 KB Output is correct
12 Correct 122 ms 51824 KB Output is correct
13 Correct 99 ms 55748 KB Output is correct
14 Correct 108 ms 46184 KB Output is correct
15 Correct 201 ms 52420 KB Output is correct
16 Correct 187 ms 51660 KB Output is correct
17 Correct 195 ms 53192 KB Output is correct
18 Correct 220 ms 57204 KB Output is correct
19 Correct 79 ms 32596 KB Output is correct
20 Correct 198 ms 52880 KB Output is correct
21 Correct 198 ms 52096 KB Output is correct
22 Correct 198 ms 53648 KB Output is correct
23 Correct 230 ms 57640 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24988 KB Output is correct
2 Correct 11 ms 25180 KB Output is correct
3 Correct 228 ms 59620 KB Output is correct
4 Correct 192 ms 61292 KB Output is correct
5 Correct 200 ms 60396 KB Output is correct
6 Correct 200 ms 61080 KB Output is correct
7 Correct 209 ms 60752 KB Output is correct
8 Correct 194 ms 59468 KB Output is correct
9 Correct 198 ms 60480 KB Output is correct
10 Correct 195 ms 59196 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24988 KB Output is correct
2 Correct 11 ms 25180 KB Output is correct
3 Correct 11 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 12 ms 25372 KB Output is correct
6 Correct 12 ms 25436 KB Output is correct
7 Correct 12 ms 25436 KB Output is correct
8 Correct 13 ms 25436 KB Output is correct
9 Correct 11 ms 25180 KB Output is correct
10 Correct 12 ms 25436 KB Output is correct
11 Correct 12 ms 25436 KB Output is correct
12 Correct 13 ms 25436 KB Output is correct
13 Correct 14 ms 25432 KB Output is correct
14 Correct 12 ms 25436 KB Output is correct
15 Incorrect 12 ms 25436 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25180 KB Output is correct
2 Correct 11 ms 24988 KB Output is correct
3 Correct 11 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 11 ms 25180 KB Output is correct
6 Correct 12 ms 25372 KB Output is correct
7 Correct 12 ms 25436 KB Output is correct
8 Correct 12 ms 25436 KB Output is correct
9 Correct 13 ms 25436 KB Output is correct
10 Correct 95 ms 45932 KB Output is correct
11 Correct 127 ms 50540 KB Output is correct
12 Correct 126 ms 50268 KB Output is correct
13 Correct 122 ms 51824 KB Output is correct
14 Correct 99 ms 55748 KB Output is correct
15 Correct 12 ms 25436 KB Output is correct
16 Correct 12 ms 25436 KB Output is correct
17 Correct 13 ms 25436 KB Output is correct
18 Correct 14 ms 25432 KB Output is correct
19 Correct 12 ms 25436 KB Output is correct
20 Incorrect 12 ms 25436 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 24988 KB Output is correct
2 Correct 11 ms 25180 KB Output is correct
3 Correct 11 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 12 ms 25372 KB Output is correct
6 Correct 12 ms 25436 KB Output is correct
7 Correct 12 ms 25436 KB Output is correct
8 Correct 13 ms 25436 KB Output is correct
9 Correct 95 ms 45932 KB Output is correct
10 Correct 127 ms 50540 KB Output is correct
11 Correct 126 ms 50268 KB Output is correct
12 Correct 122 ms 51824 KB Output is correct
13 Correct 99 ms 55748 KB Output is correct
14 Correct 108 ms 46184 KB Output is correct
15 Correct 201 ms 52420 KB Output is correct
16 Correct 187 ms 51660 KB Output is correct
17 Correct 195 ms 53192 KB Output is correct
18 Correct 220 ms 57204 KB Output is correct
19 Correct 228 ms 59620 KB Output is correct
20 Correct 192 ms 61292 KB Output is correct
21 Correct 200 ms 60396 KB Output is correct
22 Correct 200 ms 61080 KB Output is correct
23 Correct 209 ms 60752 KB Output is correct
24 Correct 194 ms 59468 KB Output is correct
25 Correct 198 ms 60480 KB Output is correct
26 Correct 195 ms 59196 KB Output is correct
27 Correct 12 ms 25436 KB Output is correct
28 Correct 12 ms 25436 KB Output is correct
29 Correct 13 ms 25436 KB Output is correct
30 Correct 14 ms 25432 KB Output is correct
31 Correct 12 ms 25436 KB Output is correct
32 Incorrect 12 ms 25436 KB Output isn't correct
33 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25180 KB Output is correct
2 Correct 11 ms 24988 KB Output is correct
3 Correct 11 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 11 ms 25180 KB Output is correct
6 Correct 12 ms 25372 KB Output is correct
7 Correct 12 ms 25436 KB Output is correct
8 Correct 12 ms 25436 KB Output is correct
9 Correct 13 ms 25436 KB Output is correct
10 Correct 95 ms 45932 KB Output is correct
11 Correct 127 ms 50540 KB Output is correct
12 Correct 126 ms 50268 KB Output is correct
13 Correct 122 ms 51824 KB Output is correct
14 Correct 99 ms 55748 KB Output is correct
15 Correct 108 ms 46184 KB Output is correct
16 Correct 201 ms 52420 KB Output is correct
17 Correct 187 ms 51660 KB Output is correct
18 Correct 195 ms 53192 KB Output is correct
19 Correct 220 ms 57204 KB Output is correct
20 Correct 228 ms 59620 KB Output is correct
21 Correct 192 ms 61292 KB Output is correct
22 Correct 200 ms 60396 KB Output is correct
23 Correct 200 ms 61080 KB Output is correct
24 Correct 209 ms 60752 KB Output is correct
25 Correct 194 ms 59468 KB Output is correct
26 Correct 198 ms 60480 KB Output is correct
27 Correct 195 ms 59196 KB Output is correct
28 Correct 12 ms 25436 KB Output is correct
29 Correct 12 ms 25436 KB Output is correct
30 Correct 13 ms 25436 KB Output is correct
31 Correct 14 ms 25432 KB Output is correct
32 Correct 12 ms 25436 KB Output is correct
33 Incorrect 12 ms 25436 KB Output isn't correct
34 Halted 0 ms 0 KB -