1229 - Sub-dictionary

[brianfry713]

The I/O in your two recent posts matches my AC code.

[flashion]

I tested my code against all your tests and still getting WA. Can you help me?

Code: Select all

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <climits>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <sstream>

#define ALL(v) v.begin(), v.end()
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REPD(i, a, b) for(int i = a; i > b; i--)
#define REPLL(i, a, b) for(ll i = a; i < b; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FORLL(i, a, b) for(ll i = a; i <= b; i++)
#define INF 1000000001

#define vit vector<int>::iterator
#define sit set<int>::iterator
#define vi vector<int>
#define vpii vector<pii >

#define ll long long
#define ld long double

#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pld pair<LD, LD>
#define st first
#define nd second

#define MAXN 102

using namespace std;

int z, n, a, b, dfs_count;
int low[MAXN], id[MAXN], vis[MAXN], vscc[MAXN], in[MAXN];
vpii nbs[MAXN];
int g[MAXN][MAXN];
string line, u, v;
map<string, int> m;
map<int, string> mr;
vector<string> res;
vector<vi > scc;
vi s;

void find_scc(int u) {
    int v;
    low[u] = id[u] = dfs_count++;
    s.PB(u);           // stores u in a vector based on order of visitation
    vis[u] = 1;
    REP(i, 0, nbs[u].size()) {
        v = nbs[u][i].st;
        if (id[v] < 0) find_scc(v);
        if (vis[v]) low[u] = min(low[u], low[v]);
    }

    if (low[u] == id[u]) {         // if this is a root (start) of an SCC
        scc.PB(vi());
        do {
            v = s.back(); s.pop_back(); vis[v] = 0;
            scc[scc.size()-1].PB(v);
        } while (u != v);
    }
}

void add(string &s) {
    if(!m.count(s)) {
        int v = m.size();
        m[s] = v;
        mr[v] = s;
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    while(true) {
        getline(cin, line);
        stringstream ss(line);
        ss >> n;
        if(!n) break;

        //cleaninng up
        REP(i, 0, n) {
            id[i] = -1;
            nbs[i].clear();
            REP(j, 0, n) g[i][j] = 0;
            scc.clear();
            res.clear();
            dfs_count = 0;
            m.clear();
            mr.clear();
            in[i] = 0;
        }

        //reading input
        REP(i, 0, n) {
            getline(cin, line);
            stringstream ss(line);
            ss >> u;
            add(u);
            while(ss >> v) {
                add(v);
                nbs[m[v]].PB(MP(m[u], 0));
            }
        }

        // finding strong connected components
        REP(i, 0, n) if(id[i] < 0) find_scc(i);

        // vscc[v] = number of scc where v belongs to
        REP(i, 0, scc.size()) REP(j, 0, scc[i].size()) {
            int v = scc[i][j];
            vscc[v] = i;
        }

        // creating graph of scc-s
        REP(i, 0, n) REP(j, 0, nbs[i].size()) {
            int u = vscc[i];
            int v = vscc[nbs[i][j].st];
            if(!g[u][v]) in[v]++;
            g[u][v] = 1;
        }

        // if scc has no incoming edges or its size() is > 1 then put in to the result vector
        REP(i, 0, scc.size()) {
            if(!in[i] || scc[i].size() > 1) {
                REP(j, 0, scc[i].size()) {
                    res.PB(mr[scc[i][j]]);
                }
            }
        }

        // sorting and printing
        sort(ALL(res));
        cout << res.size() << endl;
        REP(i, 0, res.size()) {
            cout << res[i] << (i+1 < res.size() ? " " : "");
        }
        cout << endl;
    }

    return 0;
}

[red_apricot]

// if scc has no incoming edges or its size() is > 1 then put in to the result vector

This logic may be flawed, e.g for the case

Code: Select all

3
a
b c
c b

the output is all three words. All in all, the following two are crucial test cases (just got AC):

Code: Select all

10
a b
b c
c a
d c
e d f
g e i
f g
h d
i h
j i
10
a b
b c
c a
d c
e d f
g e
f g
h d
i h
j i
0