oj.uz

Submission #983025

# Submission time Handle Problem Language Result Execution time Memory
983025 2024-05-15T07:08:22 Z shenfe1 Swapping Cities (APIO20_swap) C++17
13 / 100
 229 ms 61328 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";
  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 25180 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 12 ms 25436 KB Output is correct
6 Correct 11 ms 25436 KB Output is correct
7 Correct 11 ms 25244 KB Output is correct
8 Correct 11 ms 25432 KB Output is correct
9 Correct 93 ms 46112 KB Output is correct
10 Correct 122 ms 50632 KB Output is correct
11 Correct 118 ms 50116 KB Output is correct
12 Correct 140 ms 51804 KB Output is correct
13 Correct 100 ms 55672 KB Output is correct
14 Correct 104 ms 45992 KB Output is correct
15 Correct 197 ms 52404 KB Output is correct
16 Correct 195 ms 51740 KB Output is correct
17 Correct 194 ms 53384 KB Output is correct
18 Correct 205 ms 57220 KB Output is correct
19 Correct 77 ms 32596 KB Output is correct
20 Correct 185 ms 52680 KB Output is correct
21 Correct 179 ms 52024 KB Output is correct
22 Correct 216 ms 53628 KB Output is correct
23 Correct 207 ms 57640 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25180 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 194 ms 59612 KB Output is correct
4 Correct 192 ms 61240 KB Output is correct
5 Correct 198 ms 60400 KB Output is correct
6 Correct 229 ms 61328 KB Output is correct
7 Correct 208 ms 60696 KB Output is correct
8 Correct 185 ms 59424 KB Output is correct
9 Correct 192 ms 60360 KB Output is correct
10 Correct 210 ms 59040 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25180 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 12 ms 25436 KB Output is correct
6 Correct 11 ms 25436 KB Output is correct
7 Correct 11 ms 25244 KB Output is correct
8 Correct 11 ms 25432 KB Output is correct
9 Correct 11 ms 25176 KB Output is correct
10 Correct 11 ms 25436 KB Output is correct
11 Correct 12 ms 25496 KB Output is correct
12 Correct 13 ms 25488 KB Output is correct
13 Correct 12 ms 25436 KB Output is correct
14 Correct 13 ms 25436 KB Output is correct
15 Incorrect 15 ms 25476 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 25176 KB Output is correct
2 Correct 11 ms 25180 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 10 ms 25180 KB Output is correct
5 Correct 11 ms 25180 KB Output is correct
6 Correct 12 ms 25436 KB Output is correct
7 Correct 11 ms 25436 KB Output is correct
8 Correct 11 ms 25244 KB Output is correct
9 Correct 11 ms 25432 KB Output is correct
10 Correct 93 ms 46112 KB Output is correct
11 Correct 122 ms 50632 KB Output is correct
12 Correct 118 ms 50116 KB Output is correct
13 Correct 140 ms 51804 KB Output is correct
14 Correct 100 ms 55672 KB Output is correct
15 Correct 11 ms 25436 KB Output is correct
16 Correct 12 ms 25496 KB Output is correct
17 Correct 13 ms 25488 KB Output is correct
18 Correct 12 ms 25436 KB Output is correct
19 Correct 13 ms 25436 KB Output is correct
20 Incorrect 15 ms 25476 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 25180 KB Output is correct
2 Correct 10 ms 25180 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 11 ms 25180 KB Output is correct
5 Correct 12 ms 25436 KB Output is correct
6 Correct 11 ms 25436 KB Output is correct
7 Correct 11 ms 25244 KB Output is correct
8 Correct 11 ms 25432 KB Output is correct
9 Correct 93 ms 46112 KB Output is correct
10 Correct 122 ms 50632 KB Output is correct
11 Correct 118 ms 50116 KB Output is correct
12 Correct 140 ms 51804 KB Output is correct
13 Correct 100 ms 55672 KB Output is correct
14 Correct 104 ms 45992 KB Output is correct
15 Correct 197 ms 52404 KB Output is correct
16 Correct 195 ms 51740 KB Output is correct
17 Correct 194 ms 53384 KB Output is correct
18 Correct 205 ms 57220 KB Output is correct
19 Correct 194 ms 59612 KB Output is correct
20 Correct 192 ms 61240 KB Output is correct
21 Correct 198 ms 60400 KB Output is correct
22 Correct 229 ms 61328 KB Output is correct
23 Correct 208 ms 60696 KB Output is correct
24 Correct 185 ms 59424 KB Output is correct
25 Correct 192 ms 60360 KB Output is correct
26 Correct 210 ms 59040 KB Output is correct
27 Correct 11 ms 25436 KB Output is correct
28 Correct 12 ms 25496 KB Output is correct
29 Correct 13 ms 25488 KB Output is correct
30 Correct 12 ms 25436 KB Output is correct
31 Correct 13 ms 25436 KB Output is correct
32 Incorrect 15 ms 25476 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 25176 KB Output is correct
2 Correct 11 ms 25180 KB Output is correct
3 Correct 10 ms 25180 KB Output is correct
4 Correct 10 ms 25180 KB Output is correct
5 Correct 11 ms 25180 KB Output is correct
6 Correct 12 ms 25436 KB Output is correct
7 Correct 11 ms 25436 KB Output is correct
8 Correct 11 ms 25244 KB Output is correct
9 Correct 11 ms 25432 KB Output is correct
10 Correct 93 ms 46112 KB Output is correct
11 Correct 122 ms 50632 KB Output is correct
12 Correct 118 ms 50116 KB Output is correct
13 Correct 140 ms 51804 KB Output is correct
14 Correct 100 ms 55672 KB Output is correct
15 Correct 104 ms 45992 KB Output is correct
16 Correct 197 ms 52404 KB Output is correct
17 Correct 195 ms 51740 KB Output is correct
18 Correct 194 ms 53384 KB Output is correct
19 Correct 205 ms 57220 KB Output is correct
20 Correct 194 ms 59612 KB Output is correct
21 Correct 192 ms 61240 KB Output is correct
22 Correct 198 ms 60400 KB Output is correct
23 Correct 229 ms 61328 KB Output is correct
24 Correct 208 ms 60696 KB Output is correct
25 Correct 185 ms 59424 KB Output is correct
26 Correct 192 ms 60360 KB Output is correct
27 Correct 210 ms 59040 KB Output is correct
28 Correct 11 ms 25436 KB Output is correct
29 Correct 12 ms 25496 KB Output is correct
30 Correct 13 ms 25488 KB Output is correct
31 Correct 12 ms 25436 KB Output is correct
32 Correct 13 ms 25436 KB Output is correct
33 Incorrect 15 ms 25476 KB Output isn't correct
34 Halted 0 ms 0 KB -