oj.uz

Submission #983029

# Submission time Handle Problem Language Result Execution time Memory
983029 2024-05-15T07:11:13 Z shenfe1 Swapping Cities (APIO20_swap) C++17
6 / 100
 259 ms 57912 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 25176 KB Output is correct
2 Correct 11 ms 25180 KB Output is correct
3 Correct 11 ms 25220 KB Output is correct
4 Correct 12 ms 25180 KB Output is correct
5 Correct 15 ms 25328 KB Output is correct
6 Correct 12 ms 25320 KB Output is correct
7 Correct 14 ms 25480 KB Output is correct
8 Correct 13 ms 25436 KB Output is correct
9 Correct 104 ms 46036 KB Output is correct
10 Correct 118 ms 50704 KB Output is correct
11 Correct 109 ms 50232 KB Output is correct
12 Correct 120 ms 51652 KB Output is correct
13 Correct 99 ms 54728 KB Output is correct
14 Correct 106 ms 46020 KB Output is correct
15 Correct 188 ms 52544 KB Output is correct
16 Correct 191 ms 52004 KB Output is correct
17 Correct 190 ms 53352 KB Output is correct
18 Correct 226 ms 56452 KB Output is correct
19 Correct 77 ms 32592 KB Output is correct
20 Correct 192 ms 52720 KB Output is correct
21 Correct 202 ms 52092 KB Output is correct
22 Correct 193 ms 53904 KB Output is correct
23 Correct 259 ms 56976 KB Output is correct

Subtask #2
0 / 7.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 Incorrect 194 ms 57912 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 17.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 11 ms 25220 KB Output is correct
4 Correct 12 ms 25180 KB Output is correct
5 Correct 15 ms 25328 KB Output is correct
6 Correct 12 ms 25320 KB Output is correct
7 Correct 14 ms 25480 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 25320 KB Output is correct
11 Incorrect 12 ms 25436 KB Output isn't correct
12 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 25176 KB Output is correct
3 Correct 11 ms 25180 KB Output is correct
4 Correct 11 ms 25220 KB Output is correct
5 Correct 12 ms 25180 KB Output is correct
6 Correct 15 ms 25328 KB Output is correct
7 Correct 12 ms 25320 KB Output is correct
8 Correct 14 ms 25480 KB Output is correct
9 Correct 13 ms 25436 KB Output is correct
10 Correct 104 ms 46036 KB Output is correct
11 Correct 118 ms 50704 KB Output is correct
12 Correct 109 ms 50232 KB Output is correct
13 Correct 120 ms 51652 KB Output is correct
14 Correct 99 ms 54728 KB Output is correct
15 Correct 12 ms 25320 KB Output is correct
16 Incorrect 12 ms 25436 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 11 ms 25220 KB Output is correct
4 Correct 12 ms 25180 KB Output is correct
5 Correct 15 ms 25328 KB Output is correct
6 Correct 12 ms 25320 KB Output is correct
7 Correct 14 ms 25480 KB Output is correct
8 Correct 13 ms 25436 KB Output is correct
9 Correct 104 ms 46036 KB Output is correct
10 Correct 118 ms 50704 KB Output is correct
11 Correct 109 ms 50232 KB Output is correct
12 Correct 120 ms 51652 KB Output is correct
13 Correct 99 ms 54728 KB Output is correct
14 Correct 106 ms 46020 KB Output is correct
15 Correct 188 ms 52544 KB Output is correct
16 Correct 191 ms 52004 KB Output is correct
17 Correct 190 ms 53352 KB Output is correct
18 Correct 226 ms 56452 KB Output is correct
19 Incorrect 194 ms 57912 KB Output isn't correct
20 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 25176 KB Output is correct
3 Correct 11 ms 25180 KB Output is correct
4 Correct 11 ms 25220 KB Output is correct
5 Correct 12 ms 25180 KB Output is correct
6 Correct 15 ms 25328 KB Output is correct
7 Correct 12 ms 25320 KB Output is correct
8 Correct 14 ms 25480 KB Output is correct
9 Correct 13 ms 25436 KB Output is correct
10 Correct 104 ms 46036 KB Output is correct
11 Correct 118 ms 50704 KB Output is correct
12 Correct 109 ms 50232 KB Output is correct
13 Correct 120 ms 51652 KB Output is correct
14 Correct 99 ms 54728 KB Output is correct
15 Correct 106 ms 46020 KB Output is correct
16 Correct 188 ms 52544 KB Output is correct
17 Correct 191 ms 52004 KB Output is correct
18 Correct 190 ms 53352 KB Output is correct
19 Correct 226 ms 56452 KB Output is correct
20 Incorrect 194 ms 57912 KB Output isn't correct
21 Halted 0 ms 0 KB -