Submission #1194148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194148		Br3ad	September (APIO24_september)	C++20	100 / 100	164 ms	13504 KiB

september

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 1e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

struct DSU {
    vector<int> parent;

    DSU(int n){
        parent = vector<int>(n+1);
        iota(parent.begin(), parent.end(), 0);
    }

    int find_parent(int p){
        return (parent[p] == p)? p : parent[p] = find_parent(parent[p]);
    }

    void merge_range(int a, int b){
        if(a > b) swap(a, b);
        for(int i = a; i < b; i++){
            if(!merge(i, b)){
                // This segment has been unified
                break;
            }
        }

        for(int i = b-1; i >= a; i--){
            if(!merge(i, b)){
                // This segment has been unified also
                break;
            }
        }
    }

    bool merge(int a, int b){
        a = find_parent(a);
        b = find_parent(b);
        if(a > b) swap(a, b);
        parent[a] = b;
        return (a != b);
    }
};

vector<vector<int>> adj;
vector<bool> vis_parent, vis;

void init(int n){
    adj = vector<vector<int>>(n, vector<int>());
    vis_parent = vector<bool>(n, false);
    vis = vector<bool>(n, false);
}

int get_max_index(int cur, int prev, vector<int> &index){
    if(vis[cur]) return -1;
    vis[cur] = true;

    int max_index = index[cur];
    for(int child : adj[cur]){
        if(child == prev) continue;
        int next = get_max_index(child, cur, index);
        max_index = max(max_index, next);
    }

    return max_index;
}

// Two rules:
// 1: If a parent falls, all of its children fell
// 2: If same leaf appear in different index by different record, the range will be in same day

int solve(int n, int m, vector<int> to, vector<vector<int>> v){
    init(n);
    
    // Fill adjacency list
    for(int i = 1; i < n; i++){
        adj[i].PB(to[i]);
        adj[to[i]].PB(i);
    }

    DSU dsu(n);

    vis = vector<bool>(n, false);
    vector<vector<int>> ind(m);
    for(int i = 0; i < m; i++){
        // Process index
        vector<int> index(n);
        for(int j = 0; j < n-1; j++){
            index[v[i][j]] = j;
        }

        ind[i] = index;
        
        // Construct segment here
        queue<int> included;
        for(int j = 0; j < n-1; j++){
            if(vis[v[i][j]]) continue;

            int last_max_index = j;
            included.push(v[i][j]);
            while(!included.empty()){
                int cur = included.front();
                included.pop();

                if(vis[cur]) continue;

                int max_index = get_max_index(cur, to[cur], index);
                for(int k = last_max_index+1; k <= max_index; k++){
                    if(!vis[v[i][k]]) included.push(v[i][k]);
                }
                
                last_max_index = max(last_max_index, max_index);
            }

            dsu.merge_range(j, last_max_index);
        }
    }

    // Merge union with index of same leaf (Must be same day in the range)
    for(int i = 1; i < n; i++){
        int mn = n, mx = -1;
        for(int j = 0; j < m; j++){
            mn = min(mn, ind[j][i]);
            mx = max(mx, ind[j][i]);
        }

        dsu.merge_range(mn, mx);
    }

    int cnt = 0;
    for(int i = 0; i < n-1;){
        int par = dsu.find_parent(i);
        if(vis_parent[par]) continue;
        vis_parent[par] = true;
        cnt++;

        i = par + 1;
    }

    return cnt;
}

• 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