Submission #43016

#	Time	Username	Problem	Language	Result	Execution time	Memory
43016		RayaBurong25_1	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	153 ms	21792 KiB

oneway

#include <stdio.h>
#include <vector>
#include <cassert>
typedef struct edge edge;
struct edge
{
    int u, v;
};
std::vector<edge> E;
int inMST[100005];
std::vector<edge> AdjList[100005];
int Pa[100005];
int UF(int u)
{
    return (Pa[u] == 0)?u:(Pa[u] = UF(Pa[u]));
}
int vis[100005];
int p[100005][20];
int h[100005];
int pi[100005];
void dfsCyc(int u)
{
    // printf("dfsCyc %d\n", u);
    int i, v, s = AdjList[u].size();
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].u;
        if (v != p[u][0])
        {
            // printf("  v %d\n", v);
            p[v][0] = u;
            h[v] = h[u] + 1;
            if (E[AdjList[u][i].v - 1].u == u)
                pi[v] = AdjList[u][i].v;
            else
                pi[v] = -AdjList[u][i].v;
            dfsCyc(v);
        }
    }
}
int markCyc[100005];
char Ans[100005];
int LCA(int u, int v)
{
    int i;
    if (h[u] > h[v])
    {
        for (i = 19; i >= 0; i--)
            if (h[p[u][i]] > h[v])
                u = p[u][i];
        u = p[u][0];
    }
    if (h[v] > h[u])
    {
        for (i = 19; i >= 0; i--)
            if (h[p[v][i]] > h[u])
                v = p[v][i];
        v = p[v][0];
    }
    if (u == v)
        return u;
    for (i = 19; i >= 0; i--)
    {
        if (p[u][i] != p[v][i])
        {
            u = p[u][i];
            v = p[v][i];
        }
    }
    return p[u][0];
}
int abs(int a)
{
    return (a < 0)?-a:a;
}
void resolveCyc(int u)
{
    int i, v, s = AdjList[u].size();
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].u;
        if (v != p[u][0])
        {
            resolveCyc(v);
            markCyc[u] += markCyc[v];
        }
    }
    // printf("u%d %d\n", u, markCyc[u]);
    if (markCyc[u] > 0)
        Ans[abs(pi[u])] = 'B';
}
int markDir[100005];
void resolveDir(int u)
{
    int i, v, s = AdjList[u].size();
    for (i = 0; i < s; i++)
    {
        v = AdjList[u][i].u;
        if (v != p[u][0])
        {
            resolveDir(v);
            markDir[u] += markDir[v];
        }
    }
    if (Ans[abs(pi[u])] == 'B')
        return;
    // assert(Ans[abs(pi[u])] == 0);
    if (markDir[u] > 0)
    {
        if (pi[u] < 0)
            Ans[abs(pi[u])] = 'R';
        else
            Ans[abs(pi[u])] = 'L';
    }
    else if (markDir[u] < 0)
    {
        if (pi[u] < 0)
            Ans[abs(pi[u])] = 'L';
        else
            Ans[abs(pi[u])] = 'R';
    }
}
int main()
{
    int N, M;
    scanf("%d %d", &N, &M);
    int i, j, u, v;
    for (i = 0; i < M; i++)
    {
        scanf("%d %d", &u, &v);
        E.push_back({u, v});
    }
    int cnt = 0;
    int pu, pv;
    for (i = 0; i < M; i++)
    {
        u = E[i].u;
        v = E[i].v;
        if ((pu = UF(u)) != (pv = UF(v)))
        {
            Pa[pu] = pv;
            AdjList[u].push_back({v, i + 1});
            AdjList[v].push_back({u, i + 1});
            inMST[i] = 1;
            cnt++;
        }
    }
    for (i = 1; i <= N; i++)
    {
        if (vis[UF(i)] < 1)
        {
            dfsCyc(UF(i));
            vis[UF(i)] = 1;
        }
    }
    for (i = 1; i < 20; i++)
    {
        for (j = 1; j <= N; j++)
        {
            p[j][i] = p[p[j][i - 1]][i - 1];
        }
    }
    for (i = 0; i < M; i++)
    {
        if (!inMST[i])
        {
            markCyc[E[i].u] += 1;
            markCyc[E[i].v] += 1;
            markCyc[LCA(E[i].u, E[i].v)] += -2;
            // printf("%d + 1 %d + 1 %d - 2\n", E[i].u, E[i].v, LCA(E[i].u, E[i].v));
            Ans[i + 1] = 'B';
        }
    }
    for (i = 1; i <= N; i++)
    {
        if (vis[UF(i)] < 2)
        {
            resolveCyc(UF(i));
            vis[UF(i)] = 2;
        }
    }

    int P;
    scanf("%d", &P);
    for (i = 0; i < P; i++)
    {
        scanf("%d %d", &u, &v);
        markDir[u] += 1;
        markDir[v] += -1;
    }
    for (i = 1; i <= N; i++)
    {
        if (vis[UF(i)] < 3)
        {
            resolveDir(UF(i));
            vis[UF(i)] = 3;
        }
    }
    for (i = 1; i <= M; i++)
    {
        if (Ans[i] == 0)
            Ans[i] = 'B';
        printf("%c", Ans[i]);
    }
    // printf("\n");
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:126:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
                           ^
oneway.cpp:130:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
                               ^
oneway.cpp:184:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &P);
                    ^
oneway.cpp:187:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &u, &v);
                               ^

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