Submission #1126994

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126994		who	Rigged Roads (NOI19_riggedroads)	C++20	100 / 100	278 ms	45328 KiB

riggedroads

#include <bits/stdc++.h>

using namespace std;

#define task "palace"
#define etr "\n"
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pli pair<long long,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define bg begin
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define lwb lower_bound
#define upb upper_bound
#define range(x, l, r) x+l, x+1+r
#define all(x) (x).bg(), (x).end()
#define compact(x) x.resize(unique(all(x)) - (x).bg())
#define sq(x) ((x)*(x))

auto start = chrono::high_resolution_clock::now();

void start_timer()
{
    start = chrono::high_resolution_clock::now();
}

ld elapsed()
{
    auto current = chrono::high_resolution_clock::now();
    ld duration = chrono::duration_cast<chrono::nanoseconds>(current - start).count();
    return duration / 1e9;
}
void freop()
{
    freopen(task".inp", "r", stdin);
    freopen(task".out", "w", stdout);
}

template<class U, class V> istream& operator >> (istream& in, pair<U, V>& p)
{
    in >> p.fi >> p.se;
    return in;
}

template<class U, class V> ostream& operator << (ostream& out, pair<U, V> p)
{
    out << "{" << p.fi << ' ' << p.se << "}";
    return out;
}

template<class T> ostream& operator << (ostream& out, vector<T>& v)
{
    out << "{";
    for (int i=0; i<v.size(); i++)
    {
        out << v[i];
        if (i != v.size() - 1) out << ", ";
    }

    out << "}";
    return out;
}

const int N=3e5, M=1e5, mod=1e9+7;

int n, m;
pii edge[N+5];
int r[N+5];

namespace Sub1
{
    struct DSU
    {
        int connections = 0;
        vector<int> par;

        DSU(int sz) : par(n+5, -1) {}

        int root(int node)
        {
            return par[node] < 0 ? node : par[node] = root(par[node]);
        }

        bool connect(int u, int v)
        {
            u = root(u), v = root(v);

            if (u == v) return false;

            if (-par[u] < -par[v]) swap(u, v);

            connections++;
            par[u] += par[v];
            par[v] = u;

            return true;
        }

        bool same(int u, int v)
        {
            return root(u) == root(v);
        }
    };

    void solve()
    {
        int w[m+5];
        for (int i=1; i<=m; i++) w[i] = i;

        int tmp[m+5];
        bool mark[m+5] = {false};

        for (int i=1; i<n; i++) mark[r[i]] = true;
        do
        {
            DSU dsu(n);
            bool ok = true;
            for (int i=1; i<=m; i++) tmp[w[i]] = i;

            for (int i=1; i<=m; i++)
            {
                if (!dsu.connect(edge[tmp[i]].fi, edge[tmp[i]].se)) continue;
                if (!mark[tmp[i]])
                {
                    ok = false;
                    break;
                }
            }


            if (ok)
            {
                for (int i=1; i<=m; i++) cout << w[i] << ' ';
                return;
            }
        } while (next_permutation(range(w, 1, m)));
    }
}

namespace Sub7
{
    vector<pii> adj[N+5];
    int sub[N+5];
    int timer = 0, a[N+5], in[N+5], out[N+5], head[N+5], p[N+5];
    bool mark[N+5], used[N+5];

    struct SegmentTree
    {
        bool lazy[N*4+5];

        SegmentTree()
        {
            memset(lazy, 0, sizeof(lazy));
        }


        void update(int id, int l, int r, int pos)
        {
            if (pos<l || pos>r) return;
            if (l == r)
            {
                lazy[id] = true;
                return;
            }

            int mid = (l+r) >> 1;

            update(id*2, l, mid, pos);
            update(id*2+1, mid+1, r, pos);

            lazy[id] = lazy[id*2] && lazy[id*2+1];
        }

        int walk(int id, int l, int r, int u, int v)
        {
            if (v<l || u>r || lazy[id]) return 0;
            if (l == r) return l;

            int mid = (l+r) >> 1;
            int res;

            if (res = walk(id*2+1, mid+1, r, u, v)) return res;
            return walk(id*2, l, mid, u, v);
        }
    } seg;

    int edgeID[N+5], edgeToNode[N+5];

    int init(int par, int u)
    {
        sub[u] = 1;
        for (pii p : adj[u])
        {
            int v = p.fi;
            if (v == par) continue;
            edgeID[v] = p.se;
            edgeToNode[p.se] = v;
            sub[u] += init(u, v);
        }

        return sub[u];
    }

    void dfs(int par, int u, int hd)
    {
        head[u] = hd;
        in[u] = ++timer;
        p[u] = par;
        a[in[u]] = u;

        int child = 0;
        for (pii p : adj[u])
        {
            int v = p.fi;
            if (v == par) continue;
            if (sub[v] > sub[child]) child = v;
        }

        if (child) dfs(u, child, hd);

        for (pii p : adj[u])
        {
            int v = p.fi;
            if (v == par || v == child) continue;
            dfs(u, v, v);
        }

        out[u] = timer;
    }

    bool edgeUsed[N+5];
    vector<int> order;

    int hld(int u, int v)
    {
        //cout << u << ' ' << v << ": ";
        int dist = 0;
        vector<int> path;
        while (head[u] != head[v])
        {
            if (in[u] < in[v]) swap(u, v);

            while (true)
            {
                int node = seg.walk(1, 1, n, in[head[u]], in[u]);
                if (node == 0) break;
                //cout << a[node] << ": " << edgeID[a[node]] << "!" << etr;
                dist++;
                seg.update(1, 1, n, node);
                path.pb(edgeID[a[node]]);

            }

            u = p[head[u]];
        }

        if (u == v)
        {
            //cout << dist << etr;
            sort(all(path));

            for (int i : path)
            {
                edgeUsed[i] = true;
                order.pb(i);
            }
            return dist;
        }
        if (in[u] > in[v]) swap(u, v);

        while (true)
        {
            int node = seg.walk(1, 1, n, in[u]+1, in[v]);
            if (node == 0) break;
            //cout << a[node] << ": " << edgeID[a[node]] << "!" << etr;
            dist++;
            seg.update(1, 1, n, node);
            path.pb(edgeID[a[node]]);
        }

        sort(all(path));

        for (int i : path)
        {
            edgeUsed[i] = true;
            order.pb(i);
        }

        //cout << dist << etr;
        return dist;
    }

    int ans[N+5];

    void solve()
    {
        for (int i=1; i<n; i++)
        {
            int u = edge[r[i]].fi, v = edge[r[i]].se;
            adj[u].pb({v, r[i]});
            adj[v].pb({u, r[i]});

            mark[r[i]] = true;
        }

        init(0, 1);
        dfs(0, 1, 1);

        int cur = 1;

        for (int i=1; i<=m; i++)
        {
            if (edgeUsed[i]) continue;
            if (mark[i])
            {
                ans[i] = cur;
                used[ans[i]] = true;
                cur = ans[i] + 1;
                seg.update(1, 1, n, in[edgeToNode[i]]);
                //cout << i << ": " << ans[i] << etr;
                continue;
            }

            ans[i] = cur + hld(edge[i].fi, edge[i].se);
            //cout << i << ": " << ans[i] << etr;
            used[ans[i]] = true;
            cur = ans[i] + 1;
        }

        //cout << order << etr;

        int j = 1;
        for (int i : order)
        {
            while (used[j]) j++;
            ans[i] = j;
            used[j] = true;
        }

        for (int i=1; i<=m; i++) cout << ans[i] << ' ';
    }
};

void process()
{
    cin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        cin >> edge[i];
    }

    for (int i=1; i<n; i++) cin >> r[i];
    sort(range(r, 1, n-1));

    Sub7::solve();
    //if (m <= 9) Sub1::solve();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freop();

    int t=1; //cin >> t;
    while (t--) process();

    return 0;
}

Compilation message (stderr)

riggedroads.cpp: In function 'void freop()':
riggedroads.cpp:41:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen(task".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
riggedroads.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen(task".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 32 / 32