Submission #982110

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
982110	2024-05-13 20:42:27	Abito	Swapping Cities (APIO20_swap)	C++17	7 / 100	456 ms	524288 KiB

swap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "swap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define ep insert
#define pb push_back
using namespace std;
const int NN=4e5+5;
int n,m,c,C=INT_MAX,dis[NN],lg[NN],f[NN];
vector<pair<int,int>> adj[NN];
pair<int,int> st[25][NN],par[25][NN];
bool cmp(pair<int,int> x,pair<int,int> y){
    return x.S<y.S;
}
void dfs(int x,int p){
    dis[x]=dis[p]+1;
    st[0][++c]={dis[x],x};
    f[x]=c;
    for (auto u:adj[x]){
        if (u.F==p) continue;
        par[0][u.F]={x,u.S};
        dfs(u.F,x);
        st[0][++c]={dis[x],x};
    }return;
}
void build(){
    for (int i=1;i<25;i++) for (int j=1;j+(1<<i)<=2*n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
    for (int i=1;i<25;i++){
        for (int j=1;j<=n;j++){
            par[i][j].F=par[i-1][par[i-1][j].F].F;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27