oj.uz

Submission #468744

# Submission time Handle Problem Language Result Execution time Memory
468744 2021-08-29T14:02:34 Z Josia One-Way Streets (CEOI17_oneway) C++17
0 / 100
 0 ms 204 KB 
#include <bits/stdc++.h>

#define int int64_t

using namespace std;



struct edge {
    int from;
    int to;
    bool inUse;
    int id;
    char direction;
};

int cycleID = 1;












vector<int> chef;

int find(int x) {
    if (x == chef[x]) return x;
    return chef[x] = find(chef[x]);
}

void unite(int a, int b) {
    chef[find(a)] = find(b);
}


void init(int n) {
    for (int i = 0; i<=n; i++) {
        chef.push_back(i);
    }
}













struct DFS {


    vector<int> cycle;

    vector<bool> visited;

    vector<bool> path;
    vector<int> pathExpl;

    vector<vector<edge>> graph;



    void findCycles(int v, int id) {
        // cout << v << " ";
        // for (auto i: path) {
        //     cout << i;
        // }
        // cout << "\n";
        if (path[v]) {
            // cout << "foundCycle!\n";

            int tmp = pathExpl.size()-1;

            if (cycle[tmp] == 0)
                cycle[tmp] = cycleID;
            else
                {unite(cycle[tmp], cycleID); cycle[tmp] = cycleID;}

            while (pathExpl[tmp] != v) {
                tmp--;
                if (cycle[tmp] == 0)
                    cycle[tmp] = cycleID;
                else
                    {unite(cycle[tmp], cycleID); cycle[tmp] = cycleID;}            
            }
            cycleID++;
        }


        if (visited[v]) return;
        visited[v] = 1;

        path[v] = 1;
        pathExpl.push_back(v);

        for (edge u: graph[v]) {
            if (u.id == id) continue;
            findCycles(u.to, u.id);
        }


        path[v] = 0;
        assert(pathExpl.back() == v);
        pathExpl.pop_back();
    }

    vector<char> directions;    // single elements are overwritable...

    void init(int n) {
        cycle.assign(n, 0);
        visited.assign(n, 0);
        path.assign(n, 0);
        pathExpl.clear();
        graph.clear();
        graph.resize(n);
    }

    void addEdge(int a, int b, int id) {
        graph[a].push_back({a, b, 1, id, 'R'});
        graph[b].push_back({b, a, 1, id, 'L'});
        directions.push_back('?');
    }








    bool directionsDFS(int v, int t, int id, char dir) {
        if (visited[v]) return 0;
        visited[v] = 1;

        if (id!=-1) {
            // assert(directions[id] == '?' || directions[id] == dir || cycle[id] != 0);
            directions[id] = dir;
        }

        if (v == t) return 1;

        for (edge u: graph[v]) {
            if (directionsDFS(u.to, t, u.id, u.direction)) return 1;
        }

        if (id!=-1) directions[id] = '?';

        return 0;
    }


    void getDirections(int s, int t) {
        visited.assign(graph.size(), 0);
        directionsDFS(s, t, -1, '?');
    }
    

};



signed main() { // they may not be all connected!!!
    cin.tie(0);
    ios_base::sync_with_stdio(0);


    int n, m; cin >> n >> m;



    DFS fc;

    // cout << "\n---FINDING CYCLES---\n";

    fc.init(n);

    init(n*10);

    vector<pair<int, int>> edges;

    for (int i = 0; i<m; i++) {
        int a, b; cin >> a >> b; a--; b--;
        edges.push_back({a, b});
        fc.addEdge(a, b, i);
    }

    fc.findCycles(0, -1);


    vector<char> res(m, '?');

    assert(find(0) == 0);

    for (int i = 0; i<m; i++) {
        if (find(fc.cycle[edges[i].first]) == find(fc.cycle[edges[i].second]) && fc.cycle[edges[i].first] != 0) res[i] = 'B';
    }


    // cout << "\n---EDGES THAT ARE CYCLES---\n";

    // for (char i: res) {
    //     cout << i;
    // }

    // cout << "\n";



    int p; cin >> p;
    vector<pair<int, int>> important(p);
    for (int i = 0; i<p; i++) {
        cin >> important[i].first >> important[i].second;

        important[i].first--; important[i].second--;

        fc.getDirections(important[i].first, important[i].second);


        // cout << "\n---DIRECTIONS---\n";
        // cout << important[i].first << " " << important[i].second << "\n";
        // for (char i: fc.directions) {
        //     cout << i;
        // }
    }


    for (int i = 0; i<m; i++) {
        if (fc.directions[i]=='?') res[i] = 'B';

        if (fc.directions[i]=='L') {
            if (res[i] == '?') res[i] = 'L';
        }

        if (fc.directions[i]=='R') {
            if (res[i] == '?') res[i] = 'R';
        }
    }





    // cout << "\n---RESULT---\n";

    for (char i: res) {
        cout << i;
    }

    cout << "\n";




    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -