oj.uz

Submission #982654

# Submission time Handle Problem Language Result Execution time Memory
982654 2024-05-14T15:05:59 Z shenfe1 Swapping Cities (APIO20_swap) C++17
13 / 100
 225 ms 78920 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];
  if(mark[v]){
    mn[v]=cost[v];
  }
  for(auto to:g[v]){
    if(to==p)continue;
    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);
    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);
      // if(is)D.cycle(u,w);
    }
    else{
      D.cycle(u,w);
    }
  }
  // cerr<<1<<"\n";
  for(int i=1;i<=D.cur;i++){
    if(!mark[i])mn[i]=inf;
    else mn[i]=cost[i];
  }
  dfs1(D.get(1),D.get(1));
  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(max(mn[X],mn[Y]),cost[lca(X,Y)])==inf)return -1;
  return max(max(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 7 ms 37212 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37352 KB Output is correct
6 Correct 8 ms 37208 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 8 ms 37504 KB Output is correct
9 Correct 93 ms 61748 KB Output is correct
10 Correct 114 ms 67280 KB Output is correct
11 Correct 118 ms 64968 KB Output is correct
12 Correct 118 ms 69572 KB Output is correct
13 Correct 94 ms 73472 KB Output is correct
14 Correct 99 ms 59848 KB Output is correct
15 Correct 186 ms 69092 KB Output is correct
16 Correct 186 ms 66504 KB Output is correct
17 Correct 191 ms 71020 KB Output is correct
18 Correct 202 ms 74948 KB Output is correct
19 Correct 73 ms 45908 KB Output is correct
20 Correct 184 ms 69108 KB Output is correct
21 Correct 186 ms 68900 KB Output is correct
22 Correct 191 ms 73440 KB Output is correct
23 Correct 225 ms 77136 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37212 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 192 ms 74252 KB Output is correct
4 Correct 185 ms 78920 KB Output is correct
5 Correct 205 ms 76788 KB Output is correct
6 Correct 181 ms 77124 KB Output is correct
7 Correct 205 ms 77012 KB Output is correct
8 Correct 194 ms 74272 KB Output is correct
9 Correct 190 ms 74956 KB Output is correct
10 Correct 199 ms 74164 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37212 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37352 KB Output is correct
6 Correct 8 ms 37208 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 8 ms 37504 KB Output is correct
9 Correct 7 ms 37208 KB Output is correct
10 Correct 8 ms 37468 KB Output is correct
11 Correct 8 ms 37308 KB Output is correct
12 Correct 8 ms 37468 KB Output is correct
13 Incorrect 8 ms 37456 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37208 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 7 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37352 KB Output is correct
7 Correct 8 ms 37208 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 8 ms 37504 KB Output is correct
10 Correct 93 ms 61748 KB Output is correct
11 Correct 114 ms 67280 KB Output is correct
12 Correct 118 ms 64968 KB Output is correct
13 Correct 118 ms 69572 KB Output is correct
14 Correct 94 ms 73472 KB Output is correct
15 Correct 8 ms 37468 KB Output is correct
16 Correct 8 ms 37308 KB Output is correct
17 Correct 8 ms 37468 KB Output is correct
18 Incorrect 8 ms 37456 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37212 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 8 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37352 KB Output is correct
6 Correct 8 ms 37208 KB Output is correct
7 Correct 8 ms 37212 KB Output is correct
8 Correct 8 ms 37504 KB Output is correct
9 Correct 93 ms 61748 KB Output is correct
10 Correct 114 ms 67280 KB Output is correct
11 Correct 118 ms 64968 KB Output is correct
12 Correct 118 ms 69572 KB Output is correct
13 Correct 94 ms 73472 KB Output is correct
14 Correct 99 ms 59848 KB Output is correct
15 Correct 186 ms 69092 KB Output is correct
16 Correct 186 ms 66504 KB Output is correct
17 Correct 191 ms 71020 KB Output is correct
18 Correct 202 ms 74948 KB Output is correct
19 Correct 192 ms 74252 KB Output is correct
20 Correct 185 ms 78920 KB Output is correct
21 Correct 205 ms 76788 KB Output is correct
22 Correct 181 ms 77124 KB Output is correct
23 Correct 205 ms 77012 KB Output is correct
24 Correct 194 ms 74272 KB Output is correct
25 Correct 190 ms 74956 KB Output is correct
26 Correct 199 ms 74164 KB Output is correct
27 Correct 8 ms 37468 KB Output is correct
28 Correct 8 ms 37308 KB Output is correct
29 Correct 8 ms 37468 KB Output is correct
30 Incorrect 8 ms 37456 KB Output isn't correct
31 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37208 KB Output is correct
2 Correct 7 ms 37212 KB Output is correct
3 Correct 7 ms 37212 KB Output is correct
4 Correct 8 ms 37212 KB Output is correct
5 Correct 8 ms 37212 KB Output is correct
6 Correct 8 ms 37352 KB Output is correct
7 Correct 8 ms 37208 KB Output is correct
8 Correct 8 ms 37212 KB Output is correct
9 Correct 8 ms 37504 KB Output is correct
10 Correct 93 ms 61748 KB Output is correct
11 Correct 114 ms 67280 KB Output is correct
12 Correct 118 ms 64968 KB Output is correct
13 Correct 118 ms 69572 KB Output is correct
14 Correct 94 ms 73472 KB Output is correct
15 Correct 99 ms 59848 KB Output is correct
16 Correct 186 ms 69092 KB Output is correct
17 Correct 186 ms 66504 KB Output is correct
18 Correct 191 ms 71020 KB Output is correct
19 Correct 202 ms 74948 KB Output is correct
20 Correct 192 ms 74252 KB Output is correct
21 Correct 185 ms 78920 KB Output is correct
22 Correct 205 ms 76788 KB Output is correct
23 Correct 181 ms 77124 KB Output is correct
24 Correct 205 ms 77012 KB Output is correct
25 Correct 194 ms 74272 KB Output is correct
26 Correct 190 ms 74956 KB Output is correct
27 Correct 199 ms 74164 KB Output is correct
28 Correct 8 ms 37468 KB Output is correct
29 Correct 8 ms 37308 KB Output is correct
30 Correct 8 ms 37468 KB Output is correct
31 Incorrect 8 ms 37456 KB Output isn't correct
32 Halted 0 ms 0 KB -