oj.uz

Submission #340068

# Submission time Handle Problem Language Result Execution time Memory
340068 2020-12-26T18:18:18 Z lukameladze One-Way Streets (CEOI17_oneway) C++14
0 / 100
 9 ms 10348 KB 
# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
using namespace std;
const int N=2e5+5;
long long u,vv,n,m,t,lc,a[N],out[N],lv[N],b[N],fix[N],in[N],tin,p[N][20],low[N],brd[N];
vector < pair <long long, long long > > v[N];
long long pa[N];
map < pair <long long, long long > , long long> ans,brdg;
char ch[N];
vector <long long> v1[N];
int get_col(int a)
{
    if (a==pa[a]) return a;
    return pa[a]=get_col(pa[a]);
}
void dfs(int a, int b)
{
    fix[a]=1;
    tin++;
	in[a]=low[a]=tin;
	lv[a]=lv[b]+1;
	p[a][0]=b;
	for (int i=1; i<=18; i++)
	{
		p[a][i]=p[p[a][i-1]][i-1];
	}
    for (int i=0; i<v[a].size(); i++)
    {
        if (v[a][i].f==b) continue;
        if (fix[v[a][i].f])
        {
            low[a]=min(low[a],in[v[a][i].f]);
        }
        else
        {
            dfs(v[a][i].f,a);
            low[a]=min(low[a],low[v[a][i].f]);
            if (low[v[a][i].f]>in[a])
            {
                brdg[{v[a][i].f,a}]=1;
                 brdg[{a,v[a][i].f}]=1;
                brd[v[a][i].s]=1;
            }
        }
    }
    out[a]=tin;
}
bool upper (int a, int b)
{
	if (in[a]<=in[b] && out[a]>=out[b]) return true;
	else return false;
}
int lca(int a, int b)
{
	if (upper(b,a)) return b;
	for (int i=18; i>=0; i--)
	{
		if (p[b][i] && !upper(p[b][i],a))
		b=p[b][i];
	}
	return p[b][0];
}
int main()
{
    cin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        cin>>a[i]>>b[i];
        v[a[i]].pb({b[i],i});
        v[b[i]].pb({a[i],i});
    }
    for (int i=1; i<=n; i++)
    {
        if (!fix[i])
        {
            dfs(i,0);
        }
    }
    for (int i=1; i<=m; i++)
    {
        //if (brd[i]) cout<<a[i]<<" "<<b[i]<<endl;
    }
    for (int i=1; i<=n; i++)
    {
        pa[i]=i;
        //cout<<i<<" "<<p[i][0]<<endl;
    }
    cin>>t;
    while (t--)
    {
        cin>>u>>vv;
        lc=lca(u,vv);
        //cout<<u<<" "<<lc<<" "<<vv<<endl;
        // u--lc   lc---v
        u=get_col(u);
        while (lv[u]>lv[lc])
        {
        //    cout<<u<<" ";
            //cout<<u<<" "<<p[u][0]<<"  "<<brdg[{u,p[u][0]}]<<endl;
            if (brdg[{u,p[u][0]}] || brdg[{p[u][0],u}]) 
            {
             //   cout<<u<<"       "<<p[u][0]<<endl;
                ans[{u,p[u][0]}]=1;
            }
            pa[u]=p[u][0];
            u=get_col(u);
      //      cout<<u<<endl;
        }
      //  cout<<endl<<endl;
        vv=get_col(vv);
        while (lv[vv]>lv[lc])
        {
            if (brdg[{vv,p[vv][0]}] || brdg[{p[vv][0],vv}]) ans[{p[vv][0],vv}]=1;
            pa[vv]=p[vv][0];
            vv=get_col(vv);
        }
    }
    for (int i=1; i<=m; i++)
    {
        if (!brd[i]) 
        {
            cout<<"B";
            continue;
        }
        if (ans[{a[i],b[i]}]==1) cout<<"R";
        else if (ans[{b[i],a[i]}]==1) cout<<"L";
        else cout<<"B";
    }
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i=0; i<v[a].size(); i++)
      |                   ~^~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 8 ms 10348 KB Output is correct
5 Correct 9 ms 10348 KB Output is correct
6 Correct 7 ms 10092 KB Output is correct
7 Correct 8 ms 10348 KB Output is correct
8 Correct 9 ms 10348 KB Output is correct
9 Incorrect 9 ms 9964 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 8 ms 10348 KB Output is correct
5 Correct 9 ms 10348 KB Output is correct
6 Correct 7 ms 10092 KB Output is correct
7 Correct 8 ms 10348 KB Output is correct
8 Correct 9 ms 10348 KB Output is correct
9 Incorrect 9 ms 9964 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9836 KB Output is correct
2 Correct 7 ms 9836 KB Output is correct
3 Correct 7 ms 10092 KB Output is correct
4 Correct 8 ms 10348 KB Output is correct
5 Correct 9 ms 10348 KB Output is correct
6 Correct 7 ms 10092 KB Output is correct
7 Correct 8 ms 10348 KB Output is correct
8 Correct 9 ms 10348 KB Output is correct
9 Incorrect 9 ms 9964 KB Output isn't correct
10 Halted 0 ms 0 KB -