QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#374654#2045. Pathological PathsKKT89100 ✓1ms3600kbC++172.9kb2024-04-02 16:18:392024-04-02 16:18:40

Judging History

This is the latest submission verdict.

  • [2024-04-02 16:18:40]
  • Judged
  • Verdict: 100
  • Time: 1ms
  • Memory: 3600kb
  • [2024-04-02 16:18:39]
  • Submitted

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m, n) {
        vector<string> s(n);
        map<string, int> mp;
        set<string> st;
        for (int i = 0; i < n; i++) {
            cin >> s[i];
            mp[s[i]] = i;
            for (int j = 0; j < s[i].size(); j++) {
                if (s[i][j] == '/') {
                    st.insert(s[i].substr(0, j));
                }
            }
        }

        auto get_path_idx = [&](string &s) -> int {
            vector<string> v;
            string cur = "";
            for (int i = 1; i <= s.size(); i++) {
                if (i == s.size() or s[i] == '/') {
                    if (cur == "..") {
                        if (v.size() == 0) return -1;
                        v.pop_back();
                    } else if (cur != ".") {
                        v.push_back(cur);
                    }
                    cur = "";
                    if (i < s.size()) {
                        string str = "";
                        for (auto &p : v) {
                            str += "/" + p;
                        }
                        if (st.find(str) == st.end()) return -1;
                    }
                } else {
                    cur += s[i];
                }
            }
            string str = "";
            for (auto &p : v) {
                str += "/" + p;
            }
            if (mp.find(str) != mp.end()) return mp[str];
            else return -1;
        };

        auto slv = [&](string s) -> vector<int> {
            vector<int> res;
            if (s.back() == '/') {
                s += "index.html";
                int r = get_path_idx(s);
                if (r != -1) res.push_back(r);
            } else {
                int r = get_path_idx(s);
                if (r != -1) res.push_back(r);
                s += "/index.html";
                r = get_path_idx(s);
                if (r != -1) res.push_back(r);
            }
            return res;
        };

        for (int i = 0; i < m; i++) {
            string s, t;
            cin >> s >> t;
            auto r = slv(s), rr = slv(t);
            if (r.size() == 0 or rr.size() == 0) {
                cout << "not found\n";
            } else {
                bool ok = false;
                for (int j : r) {
                    for (int jj : rr) {
                        if (j == jj) ok = true;
                    }
                }
                if (ok) {
                    cout << "yes\n";
                } else {
                    cout << "no\n";
                }
            }
        }
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3600kb

input:

5 6
/home/ACM/index.html
/ICPC/index.html
/ICPC/general.html
/ICPC/japanese/index.html
/ICPC/secret/confidential/2005/index.html
/home/ACM/
/home/ICPC/../ACM/
/ICPC/secret/
/ICPC/secret/index.html
/ICPC
/ICPC/../ICPC/index.html
/ICPC
/ICPC/general.html
/ICPC/japanese/.././
/ICPC/japanese/./../
/home...

output:

not found
not found
yes
no
yes
not found
yes
not found
yes
yes
not found
not found
not found
yes
not found
not found
not found
not found
not found
not found
yes
yes
yes
not found
not found
not found
not found
not found
not found
no
yes
no
yes
no
yes
yes
no
not found

result:

ok 38 lines