답안 #1050630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1050630	2024-08-09T11:57:39 Z	shiocan	자매 도시 (APIO20_swap)	C++17	컴파일 오류	0 ms	0 KB

swap

#include <bits/stdc++.h>
#include <cstdlib>
#include <stdlib.h>
using namespace std;
/*
    #define cin fin
    #define cout fout
    string __fname = ""; ifstream fin(__fname + ".in"); ofstream fout(__fname + ".out");
*/
#define ull unsigned long long 
//#define ll long long
#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
ll mod = 1e9 + 7; 
//const int inf = 1e18;
//const int N = 3e5 + 100;

vector<vector<int>> a;
int n, m;

struct dsu{
    int sz = 0;
    vector<int> p, cnt;
    vector<bool> sw;
    dsu(int n, int m){
        sz = n;
        p.resize(n + m + 5);
        cnt.resize(n, 0);
        sw.resize(n + m + 5, 0);

        for(int i = 0; i < n + m + 5; i++)  
            p[i] = i;
    }

    int find(int u){
        return p[u] == u ? u : p[u] = find(p[u]);
    }

    void merge(int u, int v){
        if(u < n && v < n){
            cnt[u]++, cnt[v]++;
            if(cnt[u] > 2)
                sw[sz] = 1;
            if(cnt[v] > 2)
                sw[sz] = 1;
        }
        
        u = find(u);
        v = find(v);

        if(u == v){
            p[sz] = p[u] = sz;

            a[sz].push_back(u);
            
            sw[sz] = 1;

            sz++;
            return;
        }

        p[sz] = p[u] = p[v] = sz;
        a[sz].push_back(u);
        a[sz].push_back(v);

        if(sw[u] || sw[v])
            sw[sz] = 1;

        sz++;
    }
};

struct edge{
    int w, u, v;
};

const int K = 26;
vector<vector<int>> st;
vector<int> euler, h, first, d;

void build(vector<int> & height){
    int n = height.size();
    st = vector<vector<int>> (K, vector<int> (n+2, 0));

    for(int i = 0; i<n; i++)
        st[0][i] = i;
        
    for(int i = 1; i<K; i++)
        for(int j = 0; j + (1 << i) <= n; j++)
            if(height[st[i-1][j]] < height[st[i-1][j + (1 << (i - 1))]])
                st[i][j] = st[i-1][j];
            else
                st[i][j] = st[i-1][j + (1 << (i - 1))];
}

int get(vector<int> & height, int l, int r){
    int i = 64 - __builtin_clzll(r - l + 1) - 1;

    if(height[st[i][l]] < height[st[i][r - (1 << i) + 1]])
        return st[i][l];
    return st[i][r - (1 << i) + 1];    
}

vector<int> first_reachable, is_reachable;

void dfs(int u, int p = -1, int k = 0){
    euler.push_back(u);
    h[euler.size() - 1] = k;
    first[u] = euler.size() - 1;   

    if(p > -1 && !is_reachable[u])
        first_reachable[u] = first_reachable[p];

    for(auto i : a[u])
        if(i != p){
            dfs(i, u, k + 1);

            euler.push_back(u);
            h[euler.size() - 1] = k;
        }
}

int lca(int u, int v){
    if(first[u] > first[v])
        swap(u, v);

    return euler[get(h, first[u], first[v])];
}

vector<edge> edges;

void init(int N, int M, int u[], int v[], int w[]){
    n = N;
    m = M;

    a = vector<vector<int>> (n + m + 5);

    for(int i = 0; i<m; i++)
        edges.push_back({w[i], u[i], v[i]});

    sort(all(edges), [&] (edge a, edge b){
        return a.w < b.w;
    });

    dsu ds(n, m);

    for(auto i : edges)
        ds.merge(i.u, i.v);

    first = vector<int> (2 * (n + m + 5));
    h = vector<int> (4 * (n + m + 5));

    first_reachable = is_reachable = vector<int> (ds.sw.size(), 0ll);

    for(int i = 0; i < (int)first_reachable.size(); i++)
        if(ds.sw[i])
            is_reachable[i] = 1, first_reachable[i] = i;

    dfs(ds.sz - 1);

    build(h);
}

int getMinimumFuelCapacity(int u, int v){
    int l = lca(u, v);

    if(l >= n && is_reachable[l])
        return edges[l - n].w;
    if(first_reachable[l] >= n && is_reachable[first_reachable[l]])
        return edges[first_reachable[l] - n].w;
    return -1;
}

Compilation message

swap.cpp:15:1: error: 'll' does not name a type; did you mean 'ull'?
   15 | ll mod = 1e9 + 7;
      | ^~
      | ull