제출 #1208622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208622		overfit	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	161 ms	45124 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100003];
vector<int> num[100003];
pair<int, int> kra[100003];
char odp[100003];
bool drzewowa[100003];
bool most[100003];
int low[100003];
int pre[100003];
int aktpre = 0;
int aktspo = 0;
vector<int> spojne[100003];
int spoj[100003];
vector<int> drzewo[100003];
vector<int> numdrzewo[100003];
int jump[100003][20];

int jump2[100003];

int deep[100003];
int nextnum[100003];

bitset<100003> odwkra;
bitset<100003> odw;
bitset<100003> odwpoliczJump;
bitset<100003> odwLow;
bitset<100003> odwpolicz;
bitset<100003> odw2;

void policz(int v, int pop)
{
    odwpolicz[v] = 1;
    pre[v] = aktpre++;
    odw[v] = 1;
    for(int i = 0; i < (int)graf[v].size(); i++)
    {
        if(odw[graf[v][i]] == 0)
        {
            drzewowa[num[v][i]] = true;
            policz(graf[v][i], v);
        }
    }
}
int Low(int v, int pop, int numer)
{
    odwLow[v] = 1;
    low[v] = pre[v];
    //cout << v << "\n";
    for(int i = 0; i < (int)graf[v].size(); i++)
    {
        //cout << graf[v][i] << " " << drzewowa[num[v][i]] << "\n" ;
        if(drzewowa[num[v][i]] == false)
        {
            low[v] = min(low[v],pre[graf[v][i]]);
        }
        else if(graf[v][i] != pop && drzewowa[num[v][i]] == true)
        {
            low[v] = min(low[v],Low(graf[v][i], v, num[v][i]));
        }
    }
    if(pre[v] == low[v])
    {
        most[numer] = true;
    }
    return low[v];
}

void policzSpojne(int v)
{
    odw2[v] = 1;
    spojne[aktspo].push_back(v);
    spoj[v] = aktspo;
    for(int i = 0; i < (int)graf[v].size(); i++)
    {
        if(odw2[graf[v][i]] == 0 && most[num[v][i]] == false)
        {
            policzSpojne(graf[v][i]);
        }
    }
}

void make_tree(int v)
{
    for(auto it: spojne[v])
    {
        for(int i = 0; i < (int)graf[it].size(); i++)
        {
            if(spoj[graf[it][i]] != v)
            {
                drzewo[v].push_back(spoj[graf[it][i]]);
                numdrzewo[v].push_back(num[it][i]);
            }
        }
    }
}

void policzJump(int v, int pop, int d, int numer)
{
   // cout << v << " " << pop << " jump\n";
    odwpoliczJump[v] = 1;
    nextnum[v] = numer;
    jump[v][0] = pop;
    jump2[v] = pop;
    deep[v] = d;
    for(int i = 0; i < (int)drzewo[v].size(); i++)
    {
        if(drzewo[v][i] != pop)
        {
            policzJump(drzewo[v][i],v,d+1,numdrzewo[v][i]);
        }
    }
}

int LCA(int a, int b)
{
   // cout << a << " " << b << " lca\n";
    if(a == b)
    {
        return a;
    }
    int pot = 19;
    while(deep[a] != deep[b])
    {
       // cout << a << " " << b << " " << deep[a] << " " << deep[b] << " " << pot << " " << deep[jump[b][pot]]<< "\n";
        if(deep[a] > deep[b] && deep[jump[a][pot]] >= deep[b])
        {
            a = jump[a][pot];
        }
        else if(deep[b] > deep[a] && deep[jump[b][pot]] >= deep[a])
        {
            b = jump[b][pot];
        }
        pot--;
    }
    if(a == b)
    {
        return a;
    }
    for(int i = 19; i > -1; i--)
    {
        if(jump[a][i] != jump[b][i])
        {
            a = jump[a][i];
            b = jump[b][i];
        }
    }
    return jump[a][0];
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a,b;
        cin >> a >> b;
        kra[i+1] = {a,b};
        graf[a].push_back(b);
        graf[b].push_back(a);
        num[a].push_back(i+1);
        num[b].push_back(i+1);
        odp[i+1] = 'B';
    }
    for(int i = 1; i <= n; i++)
    {
        if(odwpolicz[i] == 0)
        {
            policz(i,-1);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(odwLow[i] == 0)
        {
            Low(i,-1,0);
        }
    }
    for(int i = 1; i <= n; i++)
    {
        if(odw2[i] == 0)
        {
            policzSpojne(i);
            aktspo++;
        }
    }
    for(int i = 0; i < aktspo; i++)
    {
        make_tree(i);
    }
    for(int i = 0; i < aktspo; i++)
    {
        if(odwpoliczJump[i] == 0)
        {
            policzJump(i,0,0,0);
        }
    }
    for(int i = 1; i < 20; i++)
    {
        for(int j = 0; j <= aktspo; j++)
        {
            jump[j][i] = jump[jump[j][i-1]][i-1];
        }
    }
  //  for(int i = 0; i < aktspo; i++)
  //  {
   //     cout << i << "    ";
   //     for(auto& it: spojne[i]) cout << it << " ";
    //    cout << "\n";
  //  }
    int q;
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        int a,b;
        cin >> a >> b;
        int a2 = spoj[a];
        int b2 = spoj[b];
        a = spoj[a];
        b = spoj[b];
        int lca = LCA(a,b);
        vector<int> va;
        vector<int> vb;
       // cout << "\nlca " << lca << " \n\n";
       // cout << a << " a\n";
        while(deep[a] > deep[lca])
        {
            
            odwkra[nextnum[a]] = 1;
            if(spoj[kra[nextnum[a]].first] == a)
            {
                odp[nextnum[a]] = 'R';
            }
            else
            {
                odp[nextnum[a]] = 'L';
            }
            va.push_back(a);
            a = jump2[a];
            //cout << a << " a\n";
           
        }
        //cout << "\n";
        //cout << b << " b\n";
        while(deep[b] > deep[lca])
        {
            odwkra[nextnum[b]] = 1;
            if(spoj[kra[nextnum[b]].first] == b)
            {
                odp[nextnum[b]] = 'L';
            }
            else
            {
                odp[nextnum[b]] = 'R';
            }
            vb.push_back(b);
            b = jump2[b];
           // cout << b << " b\n";
        }
        for(auto& it: va) jump2[it] = a;
        for(auto& it: vb) jump2[it] = b;
        //cout << "\n";
    }
    for(int i = 1; i <= m; i++)
    {
        cout << odp[i];
    }
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40