Submission #1084338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1084338		79brue	September (APIO24_september)	C++17	100 / 100	329 ms	29680 KiB

september

#include "september.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct segTree{
    int tree[400002];

    void init(int i, int l, int r){
        tree[i] = 0;
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
    }

    void update(int i, int l, int r, int x, int v){
        if(l==r){
            tree[i] = v;
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    int query(int i, int l, int r, int v){ /// [1, i] 최댓값이 v보다 큰 인 최소 i 반환
        if(tree[i] <= v) return -1;
        if(l==r) return l;
        int m = (l+r)>>1;
        if(tree[i*2] > v) return query(i*2, l, m, v);
        else return query(i*2+1, m+1, r, v);
    }
} tree;

struct UnionFind{
    int par[100002];
    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int x){
        if(x == par[x]) return x;
        return x = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        if(x>y) swap(x, y);
        par[y] = x;
    }
} dsu[5];

struct Query{
    int a, b;
    Query(int a, int b): a(a), b(b){}
};

int n, m;
int par[100002];
vector<int> link[100002];
int arr[5][100002], ord[5][100002];
int DP[100002];

void dfs(int x){
    for(int y: link[x]){
        if(x) DP[y] = min(DP[y], DP[x]);
        dfs(y);
    }
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	n = N, m = M;
	for(int i=1; i<n; i++) par[i] = F[i], link[par[i]].push_back(i);
	for(int i=0; i<m; i++) for(int j=1; j<N; j++){
        arr[i][j] = S[i][j-1];
        ord[i][arr[i][j]] = j;
	}

	vector<Query> queries;

    /// Case 1
    for(int d=0; d<m-1; d++){
        tree.init(1, 1, n-1);
        for(int i=1; i<n; i++){
            int x = tree.query(1, 1, n-1, ord[d+1][arr[d][i]]);
            if(x != -1) queries.push_back(Query(arr[d][x], arr[d][i]));
            tree.update(1, 1, n-1, i, ord[d+1][arr[d][i]]);
        }
    }

    /// Case 2
    for(int d=0; d<m; d++){
        for(int i=0; i<n; i++) DP[i] = ord[d][i];
        dfs(0);
        for(int i=0; i<n; i++){
            if(DP[i] < ord[d][i]){
                queries.push_back(Query(arr[d][DP[i]], i));
            }
        }
    }

    /// 본격 작업 시작
    for(int d=0; d<m; d++) dsu[d].init(n-1);

    while(!queries.empty()){
        int A = queries.back().a, B = queries.back().b; queries.pop_back();
        for(int d=0; d<m; d++){
            int ad = dsu[d].find(ord[d][A]), bd = dsu[d].find(ord[d][B]);
            if(ad > bd) swap(ad, bd);
            while(ad != bd){
                queries.push_back(Query(arr[d][bd-1], arr[d][bd]));
                dsu[d].merge(bd-1, bd);
                bd = dsu[d].find(bd);
            }
        }
    }

    int ans = 0;
    for(int i=1; i<n; i++) if(dsu[0].find(i) == i) ans++;

    /// 초기화
    for(int i=0; i<=n; i++){
        link[i].clear();
        DP[i] = 0;
    }

    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16