tough contest

C is tough!

Cool contest, especially $$$B$$$ & $$$C$$$. Maybe there is easier solution, i solved $$$B$$$ using segtree(it is straightforward to find such index $$$f$$$, that after an operation on $$$v[f : f + k - 1]$$$, $$$v$$$ is maximal. We can compare results of operations $$$v[x: x + k - 1]$$$, $$$v[y : y + k - 1]$$$ in $$$O(\log n)$$$.) $$$C$$$ is pretty cool too. Thanks!

I passed D in the last 2sec!!!!!

my submission

how to solve A

edit : solved

is this code O(n^2)? https://atcoder.jp/contests/arc165/submissions/45684077 or did i make a error somewhere.

(I asserted some places, so i do think its O(n^2))

(The Solution is to find scc, condense them, refind scc. i pass a graph of size atmost m atmost n times and my m pointers also move atmost n times, so i believe its n^2)

B test cases too weak
Passed with checking for the last 100 indexes and indices of elements 1...200 and taking the best of them
https://atcoder.jp/contests/arc165/submissions/45673283

First time in Top 10!

Also, problem F is really similar to IOI19 arranging shoes. F just added "lexiographically smallest" to IOI19 shoes, but it made the implementation way harder.

Are tests for B too weak? Looking at first python AC solution: https://atcoder.jp/contests/arc165/submissions/45672082

It seems like it should fail for something like:

4 3
3 4 1 2

It outputs 1 3 4 2. I think it should be 3 1 2 4

I have little difference with editorial in solution to $$$C$$$. I calculate the maximum $$$x$$$, such that if we remove edges with $$$w \ge x$$$, graph is bipartite. I use binary search for it. Let it be $$$A$$$. But then I don't calcalute minimum weight of path with length $$$2$$$ for remaining edges. Instead, in the whole graph I calculate minimum weight $$$B$$$ of path with length $$$2$$$, only once. The answer is $$$min(A, B)$$$.

I wrote I solution to C using binary search and checking whether the graph bipartite. But is gets WA, I have no idea why. I was debugging it for an hour, then I wrote a DSU solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#pragma GCC optimize("unroll-loops,O3")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt,sse4.2")
#define cok cout << (ok ? "YES\n" : "NO\n");
#define dbg(x) cout << (#x) << ": " << x << endl;
#define dbga(x,l,r) cout << (#x) << ": "; for (int ii=l;ii<r;ii++) cout << x[ii] << " "; cout << endl;
#define int long long
#define pi pair<int, int>
const int N = 1e6+9;
vector<pi> vec[N], g[N];
int used[N];
int n, m;
int ch()
{
    int ans = 2e9 + 100;
    for (int i=0;i<n;i++)
    {
        multiset<int> st;
        for (auto [b, c]: vec[i]) st.insert(c);
        if (st.size() > 1)
        {
            int tek = 0;
            auto it = st.begin();
            tek += *it;
            it++;
            tek += *it;
            ans = min(ans, tek);
        }
    }
    return ans;
}
bool good(int mid)
{
    for (int i=0;i<n;i++) used[i] = 0;
    queue<int> q;
    used[0] = 1;
    q.push(0);
    while (q.size())
    {
        int v = q.front();
        q.pop();
        for (auto [u, c]: g[v])
        {
            if (!used[u])
            {
                used[u] = used[v] == 1 ? 2 : 1;
                q.push(u);
            }
            else
            {
                if (used[u] == used[v]) return 0;
            }
        }
    }
    return 1;
}
signed main()
{
    cin.tie(0);ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for (int i=0;i<m;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--;b--;
        vec[a].pb({b, c});
        vec[b].pb({a, c});
    }
    for (int i=0;i<n;i++) g[i] = vec[i];
    if (good(2e9 + 100))
    {
        cout << ch();
        return 0;  
    }
    int l = 0, r = ch() + 1;
    while (r - l > 1)
    {
        int mid = (l + r) / 2;
        for (int i=0;i<n;i++) {
            g[i].clear();
            for (auto [b, c]: vec[i])
            {
                if (c < mid) g[i].pb({b, c});
            }
        }
        if (good(mid)) l = mid;
        else r = mid;
    }
    cout << l;
}

Why is this solution correct for B? On the following input
6 3
6 3 2 5 1 4
The program outputs
6 3 1 2 5 4
When we can obtain
6 3 2 1 4 5
By applying operation on the last 3 elements. Please can anyone tell me what i am missing?

How to (or, Can we) add hacks for B? Tests are too weak.

As some of you mentioned, tests for B were weak. We added a few extra tests as after_contest.

In second solution of C can someone explain me how to find the weight of the edge at which the graph first becomes non-bipartite when starting from a graph with N vertices and 0 edges and adding M edges in ascending order of weight. I wasn't able to understand how the approach given in the editorial works to find this.