oj.uz

Submission #982644

# Submission time Handle Problem Language Result Execution time Memory
982644 2024-05-14T14:40:39 Z shenfe1 Swapping Cities (APIO20_swap) C++17
13 / 100
 203 ms 44760 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=3e5+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];
  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 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);
    }
    else{
      D.cycle(u,w);
    }
  }
  // cerr<<1<<"\n";
  for(int i=1;i<=D.cur;i++)mn[i]=inf;
  dfs(D.get(1),D.get(1));
  // for(int i=1;i<=D.cur;i++)cout<<i<<" "<<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<<lca(X,Y)<<" "<<up[X][19]<<"\n";
  // cout<<cost[lca(X,Y)]<<" "<<mn[X]<<" "<<mn[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 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 14892 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 73 ms 34028 KB Output is correct
10 Correct 92 ms 36524 KB Output is correct
11 Correct 93 ms 36256 KB Output is correct
12 Correct 95 ms 36960 KB Output is correct
13 Correct 80 ms 40064 KB Output is correct
14 Correct 77 ms 32732 KB Output is correct
15 Correct 173 ms 38084 KB Output is correct
16 Correct 157 ms 37784 KB Output is correct
17 Correct 165 ms 38344 KB Output is correct
18 Correct 186 ms 41416 KB Output is correct
19 Correct 65 ms 21588 KB Output is correct
20 Correct 183 ms 38396 KB Output is correct
21 Correct 163 ms 39404 KB Output is correct
22 Correct 169 ms 39804 KB Output is correct
23 Correct 203 ms 42928 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 167 ms 44224 KB Output is correct
4 Correct 169 ms 44760 KB Output is correct
5 Correct 190 ms 44508 KB Output is correct
6 Correct 172 ms 44720 KB Output is correct
7 Correct 195 ms 44720 KB Output is correct
8 Correct 185 ms 44068 KB Output is correct
9 Correct 181 ms 44740 KB Output is correct
10 Correct 170 ms 43992 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 14892 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 3 ms 14684 KB Output is correct
10 Correct 3 ms 14684 KB Output is correct
11 Incorrect 3 ms 14684 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 4 ms 14892 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 73 ms 34028 KB Output is correct
11 Correct 92 ms 36524 KB Output is correct
12 Correct 93 ms 36256 KB Output is correct
13 Correct 95 ms 36960 KB Output is correct
14 Correct 80 ms 40064 KB Output is correct
15 Correct 3 ms 14684 KB Output is correct
16 Incorrect 3 ms 14684 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 4 ms 14892 KB Output is correct
6 Correct 3 ms 14684 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14940 KB Output is correct
9 Correct 73 ms 34028 KB Output is correct
10 Correct 92 ms 36524 KB Output is correct
11 Correct 93 ms 36256 KB Output is correct
12 Correct 95 ms 36960 KB Output is correct
13 Correct 80 ms 40064 KB Output is correct
14 Correct 77 ms 32732 KB Output is correct
15 Correct 173 ms 38084 KB Output is correct
16 Correct 157 ms 37784 KB Output is correct
17 Correct 165 ms 38344 KB Output is correct
18 Correct 186 ms 41416 KB Output is correct
19 Correct 167 ms 44224 KB Output is correct
20 Correct 169 ms 44760 KB Output is correct
21 Correct 190 ms 44508 KB Output is correct
22 Correct 172 ms 44720 KB Output is correct
23 Correct 195 ms 44720 KB Output is correct
24 Correct 185 ms 44068 KB Output is correct
25 Correct 181 ms 44740 KB Output is correct
26 Correct 170 ms 43992 KB Output is correct
27 Correct 3 ms 14684 KB Output is correct
28 Incorrect 3 ms 14684 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14684 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 3 ms 14684 KB Output is correct
4 Correct 3 ms 14684 KB Output is correct
5 Correct 3 ms 14684 KB Output is correct
6 Correct 4 ms 14892 KB Output is correct
7 Correct 3 ms 14684 KB Output is correct
8 Correct 3 ms 14684 KB Output is correct
9 Correct 3 ms 14940 KB Output is correct
10 Correct 73 ms 34028 KB Output is correct
11 Correct 92 ms 36524 KB Output is correct
12 Correct 93 ms 36256 KB Output is correct
13 Correct 95 ms 36960 KB Output is correct
14 Correct 80 ms 40064 KB Output is correct
15 Correct 77 ms 32732 KB Output is correct
16 Correct 173 ms 38084 KB Output is correct
17 Correct 157 ms 37784 KB Output is correct
18 Correct 165 ms 38344 KB Output is correct
19 Correct 186 ms 41416 KB Output is correct
20 Correct 167 ms 44224 KB Output is correct
21 Correct 169 ms 44760 KB Output is correct
22 Correct 190 ms 44508 KB Output is correct
23 Correct 172 ms 44720 KB Output is correct
24 Correct 195 ms 44720 KB Output is correct
25 Correct 185 ms 44068 KB Output is correct
26 Correct 181 ms 44740 KB Output is correct
27 Correct 170 ms 43992 KB Output is correct
28 Correct 3 ms 14684 KB Output is correct
29 Incorrect 3 ms 14684 KB Output isn't correct
30 Halted 0 ms 0 KB -