Submission #771501

#	Time	Username	Problem	Language	Result	Execution time	Memory
771501		Amylopectin	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	69 ms	33728 KiB

oneway

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int mxn = 1e6 + 10,mxi = 1e9 + 10;
struct we
{
    int to,idx,dir;
};
vector<struct we> pat[mxn] = {};
int par[mxn] = {},vall[mxn] = {},u[mxn] = {},dep[mxn] = {};
char ans[mxn] = {};
int fimi(int l,int r)
{
    if(l < r)
    {
        return l;
    }
    return r;
}
int re(int cn,int cidx,int cdir)
{
    int i,j,fn,fidx,fdir,ret = mxi,cva;
    u[cn] = 1;
    for(i=0; i<pat[cn].size(); i++)
    {
        fn = pat[cn][i].to;
        fidx = pat[cn][i].idx;
        fdir = pat[cn][i].dir;
        if(fidx == cidx)
        {
            continue;
        }
        if(u[fn] == 1)
        {
            ans[fidx] = 'B';
            ret = fimi(ret,dep[fn]);
            continue;
        }
        dep[fn] = dep[cn] + 1;
        cva = re(fn,fidx,fdir);
        ret = fimi(ret,cva);
        vall[cn] += vall[fn];
    }
    if(cidx == -1)
    {
        return 0;
    }
    if(ret < dep[cn] || vall[cn] == 0)
    {
        ans[cidx] = 'B';
    }
    else 
    {
        if(vall[cn] < 0)
        {
            if(cdir == 0)
            {
                ans[cidx] = 'L';
            }
            else 
            {
                ans[cidx] = 'R';
            }
        }
        else 
        {
            if(cdir == 0)
            {
                ans[cidx] = 'R';
            }
            else 
            {
                ans[cidx] = 'L';
            }
        }
    }
    return ret;
}
int main()
{
    int i,j,q,k,n,m,cn,cm,fn,fm,roo = 1;
    scanf("%d %d",&n,&m);
    for(i=0; i<m; i++)
    {
        scanf("%d %d",&cn,&cm);
        pat[cn].push_back({cm,i,1});
        pat[cm].push_back({cn,i,0});
    }
    scanf("%d",&q);
    for(i=0; i<q; i++)
    {
        scanf("%d %d",&cn,&cm);
        vall[cn] ++;
        vall[cm] --;
    }
    for(i=1; i<=n; i++)
    {
        if(u[i] == 0)
        {
            dep[i] = 0;
            re(i,-1,-1);
        }
    }
    printf("%s\n",ans);
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int re(int, int, int)':
oneway.cpp:26:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<we>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(i=0; i<pat[cn].size(); i++)
      |              ~^~~~~~~~~~~~~~~
oneway.cpp:24:11: warning: unused variable 'j' [-Wunused-variable]
   24 |     int i,j,fn,fidx,fdir,ret = mxi,cva;
      |           ^
oneway.cpp: In function 'int main()':
oneway.cpp:83:11: warning: unused variable 'j' [-Wunused-variable]
   83 |     int i,j,q,k,n,m,cn,cm,fn,fm,roo = 1;
      |           ^
oneway.cpp:83:15: warning: unused variable 'k' [-Wunused-variable]
   83 |     int i,j,q,k,n,m,cn,cm,fn,fm,roo = 1;
      |               ^
oneway.cpp:83:27: warning: unused variable 'fn' [-Wunused-variable]
   83 |     int i,j,q,k,n,m,cn,cm,fn,fm,roo = 1;
      |                           ^~
oneway.cpp:83:30: warning: unused variable 'fm' [-Wunused-variable]
   83 |     int i,j,q,k,n,m,cn,cm,fn,fm,roo = 1;
      |                              ^~
oneway.cpp:83:33: warning: unused variable 'roo' [-Wunused-variable]
   83 |     int i,j,q,k,n,m,cn,cm,fn,fm,roo = 1;
      |                                 ^~~
oneway.cpp:84:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:87:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
oneway.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         scanf("%d %d",&cn,&cm);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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