Submission #1136376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136376		jerzyk	Simurgh (IOI17_simurgh)	C++20	100 / 100	274 ms	53712 KiB

simurgh

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 1000'007;
int fau[N];
int clr[N];
pair<int, int> e[N];
int vis[N];
vector<pair<int, int>> ed[N], ed2[N];
vector<int> drz; int ildrz = 0;
int o[N], oe[N], wys[N];

int Find(int v)
{
    if(fau[v] == v) return v;
    return (fau[v] = Find(fau[v]));
}

void Union(int a, int b)
{
    fau[Find(b)] = Find(a);
}

void DFSD(int v)
{
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        if(wys[ed[v][i].st] != 0) continue;
        o[ed[v][i].st] = v; oe[ed[v][i].st] = ed[v][i].nd;
        wys[ed[v][i].st] = wys[v] + 1;
        drz.pb(ed[v][i].nd);
        ed2[v].pb(ed[v][i]);
        ed2[ed[v][i].st].pb(make_pair(v, ed[v][i].st));
        DFSD(ed[v][i].st);
    }
}

int DoDQ(int ol, int nw)
{
    vector<int> q;
    q = drz;
    for(int i = 0; i < (int)drz.size(); ++i)
        if(q[i] == ol) q[i] = nw;
    return count_common_roads(q) - ildrz;
}


void DFS(int v)
{
    //cerr << v << "\n";
    for(int i = 0; i < (int)ed2[v].size(); ++i)
    {
        if(o[v] == ed2[v][i].st) continue;
        DFS(ed2[v][i].st);
    }
    if(v == 0) return;
    pair<int, int> bst = make_pair(N, N);
    for(int i = 0; i < (int)ed[v].size(); ++i)
        if(ed[v][i].nd != oe[v])
            bst = min(bst, make_pair(wys[ed[v][i].st], ed[v][i].nd));
    if(bst.st >= wys[v])
    {
        if(clr[oe[v]] == 0)
            clr[oe[v]] = 1;
        return;
    }
    vector<int> pth, qu;
    int x = v;
    while(wys[x] != bst.st)
    {
        pth.pb(oe[x]);
        x = o[x];
    }
    for(int i = 0; i < (int)pth.size(); ++i)
    {
        int cur = 0;
        if(clr[pth[i]] == 0)
        {
            cur = DoDQ(pth[i], bst.nd);
            if(cur == 1)
                {clr[pth[i]] = -1; clr[bst.nd] = 1;}
            if(cur == -1)
                {clr[pth[i]] = 1; clr[bst.nd] = -1;}
            if(cur == 0)
                if(clr[bst.nd] != 0)
                    clr[pth[i]] = clr[bst.nd];
        }else
        {
            if(clr[bst.nd] == 0)
            {
                cur = DoDQ(pth[i], bst.nd);
                if(cur == 0)
                    clr[bst.nd] = clr[pth[i]];
                else
                    clr[bst.nd] = clr[pth[i]] * -1;
            }
        }
        qu.pb(cur);
    }
    if(clr[bst.nd] == 0)
        clr[bst.nd] = -1;
    for(int i = 0; i < (int)pth.size(); ++i)
    {
        if(clr[pth[i]] != 0) continue;
        if(qu[i] == 0)
            clr[pth[i]] = clr[bst.nd];
        else
            clr[pth[i]] = clr[bst.nd] * -1;
    }
}

int Fill(vector<int> &akt)
{
    int s = 0;
    for(int i = 0; i < (int)drz.size(); ++i)
    {
        if(Find(e[drz[i]].st) != Find(e[drz[i]].nd))
        {
            Union(e[drz[i]].st, e[drz[i]].nd);
            if(clr[drz[i]] == 1)
                ++s;
            akt.pb(drz[i]);
        }
    }
    return s;
}

int Ilt(vector<int> &q)
{
    int d = Fill(q);
    return count_common_roads(q) - d;
}

int DoS(int n, int m)
{
    //cerr << "DoS:\n";
    vector<int> cur, qu;
    for(int i = 0; i < n; ++i) fau[i] = i;
    for(int i = 0; i < m; ++i)
    {
        if(clr[i] != 0 || vis[i]) continue;
        if(Find(e[i].st) != Find(e[i].nd))
        {
            //cerr << i << "\n";
            cur.pb(i);
            vis[i] = 1;
            Union(e[i].st, e[i].nd);
        }
    }
    if((int)cur.size() == 0) return -1;
    qu = cur;
    int ilw = Ilt(qu);
    
    //cerr << ilw << "\n";
    
    for(int xd = 1; xd <= ilw; ++xd)
    {
        int p = 0, k = (int)cur.size() - 1, s;
        while(p < k)
        {
            qu.clear();
            s = (p + k) / 2;
            for(int i = 0; i < n; ++i) fau[i] = i;
            for(int i = 0; i <= s; ++i)
            {
                qu.pb(cur[i]);
                Union(e[cur[i]].st, e[cur[i]].nd);
            }
            if(Ilt(qu) == 0)
                p = s + 1;
            else
                k = s;
        }
        clr[cur[p]] = 1;
        swap(cur[p], cur.back());
        cur.pop_back();
    }
    return 1;
}

vector<int> find_roads(int _n, vector<int> _u, vector<int> _v)
{
    int n = _n, m = (int)_u.size();
    for(int i = 0; i <= n; ++i) fau[i] = i;
    for(int i = 0; i < m; ++i)
    {
        e[i] = make_pair(_u[i], _v[i]);
        ed[_u[i]].pb(make_pair(_v[i], i));
        ed[_v[i]].pb(make_pair(_u[i], i));
    }
    wys[0] = 1;
    DFSD(0);
    ildrz = count_common_roads(drz);
    DFS(0);
    /*for(int i = 0; i < m; ++i)
        cerr << "E: " << i << " " << clr[i] << "\n";
    for(int i = 1; i < n; ++i)
        cerr << "UE: " << i << " " << o[i] << " " << clr[oe[i]] << "\n";*/

    int v = DoS(n, m);
    while(v != -1)
        v = DoS(n, m);
    vector<int> answer;
    for(int i = 0; i < m; ++i)
        if(clr[i] == 1)
            answer.pb(i);
    return answer;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30