Google Code Jam 2010 Round 1B Problem A. File Fix-it

Problem

/home/gcj/finals

mkdir /home

mkdir /home/gcj

mkdir /home/gcj/finals

mkdir /home/gcj/quals

Input

Output

Limits

Small dataset

Large dataset

Sample

Input	Output
3 0 2 /home/gcj/finals /home/gcj/quals 2 1 /chicken /chicken/egg /chicken 1 3 /a /a/b /a/c /b/b	Case #1: 4 Case #2: 0 Case #3: 4

Solution

map<string, bool>existing;

vector<string>wanted;

int solve()

{

    int nc = ;

    for (int w = ; w < wanted.size(); w++) {

        string wp = wanted.at(w);

        int wplen = (int)wp.length();

        for (int p = ; p <= wplen; p++) {

            if (wp[p] == '/' || p == wplen) {

                string pc = wp.substr(, p);

                if (!existing.count(pc)) {

                    nc++;

                    existing.insert(pair<string, bool>(pc, true));

                }

            }

        }

    }

    return nc;

}

int main()

{

    freopen("in.in", "r", stdin);

    freopen("out.out", "w", stdout);

    int T;

    scanf("%d\n", &T);

    if (!T) {

        cerr << "Check input!" << endl;

        exit();

    }

    for (int t = ; t <= T; t++) {

        cerr << "Solving: #" << t << " / " << T << endl;

        int N, M;

        scanf("%d %d\n", &N, &M);

        existing.clear();

        wanted.clear();

        for (int i = ; i < N; i++) {

            string path;

            cin >> path;

            existing.insert(pair<string, bool>(path, true));

        }

        for (int i = ; i < M; i++) {

            string path;

            cin >> path;

            wanted.push_back(path);

        }

        auto result = solve();

        printf("Case #%d: %d\n", t, result);

    }

    fclose(stdin);

    fclose(stdout);

    return ;

}