QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#374654 | #2045. Pathological Paths | KKT89 | 100 ✓ | 1ms | 3600kb | C++17 | 2.9kb | 2024-04-02 16:18:39 | 2024-04-02 16:18:40 |
Judging History
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