oj.uz

Submission #486732

# Submission time Handle Problem Language Result Execution time Memory
486732 2021-11-12T14:50:22 Z pppickleman One-Way Streets (CEOI17_oneway) C++11
0 / 100
 1 ms 460 KB 
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

int n, m, a, b, l, p;
int pre[1000];
int ind[1000];
pii edge[1000];
int back[1000];
int val[1000];
int val2[1000];
int starts[100];
int finishes[100];
int visited[1000];
char dir[1000];
vector<int> cycle;
vector<int> adj[1000];
string ans;

int next(pii x, int u)
{
    return x.f ^ x.s ^ u;
}

void dfs(int n)
{    
    for (auto e : adj[n]){
        int v = next(edge[e], n);

        if (v != pre[n]){
            if (ind[v] == 1e9){
                ind[v] = min(ind[v], ind[n] + 1);
                pre[v] = n;
                cout << n + 1 << " " << v + 1 << " tree edge" << endl;
                dfs(v);
                val[n] += val[v];
                if (val[v] != 0)
                    cycle.push_back(e);
            } else {
                if (ind[v] <= ind[n]){
                    cout << n + 1 << " " << v + 1 << " back edge" << endl;
                    val[n]++;
                    val[v]--;
                    cycle.push_back(e);
                    dir[e] = 'B';
                }
            }
        }
    }
}

void dfs2(int n)
{
    for (auto e : adj[n]){
        int v = next(edge[e], n);

        if (ind[n] <= ind[v] && dir[e] != 'B'){
            cout << "dfs: " << n + 1 << " -> " << v + 1 << endl;
            dfs2(v);
            cout << n + 1 << ": " << val2[n];
            val2[n] += val2[v];
            cout << " + " << val2[v] << " = " << val2[n] << endl;
        }
    }
}

int main ()
{
    cin >> n >> m;

    int rept;

    for (int i = 0; i < m; i++){
        cin >> a >> b;
        rept = 0;
        for (int j = 0; j < sizeof(adj[a - 1]); j++){
            if (b - 1 == next(edge[adj[a - 1][j]], a - 1))
                rept = 1;
        }
        if (rept == 0){
            edge[i].f = a - 1;
            edge[i].s = b - 1;
            adj[a - 1].push_back(i);
            adj[b - 1].push_back(i);
        }
    }

    for (int i = 0; i < n; i++){
        ind[i] = 1e9;
    }

    ind[0] = 1;

    memset(val, 0, sizeof(val));

    dfs(0);
 
    for (auto e : cycle){
        cout << e << endl;
    }

    cin >> p;

    for (int i = 0; i < p; i++){
        cin >> a >> b;
        starts[i] = a - 1;
        finishes[i] = b - 1;
    }

    memset(val2, 0, sizeof(val));

    for (int i = 0; i < p; i++){
        val2[starts[i]]++;
        val2[finishes[i]]--;
    }

    for (int i = 0; i < n; i++){
        cout << i << " val is " << val2[i] << endl;
    }

    dfs2(0);

    for (int i = 0; i < n; i++)
        cout << i + 1 << " = " << val2[i] << endl;

    int k;

    for (int i = 0; i < m; i++){
        if (ind[edge[i].f] > ind[edge[i].s])
            k = val2[edge[i].f];
        else
            k = val2[edge[i].s];
        
        if (k > 0)
            dir[i] = 'R';
        else if (k < 0)
            dir[i] = 'L';
        else
            dir[i] = 'B';
    }

    for (int i = 0; i < m; i++)
        cout << dir[i] << " ";
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'long unsigned int' [-Wsign-compare]
   80 |         for (int j = 0; j < sizeof(adj[a - 1]); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -