Absolute Path Of A Targeted File Where The Virus Is Not Present!!

Arunima Mandal

Problem: https://domjudge.cs.fsu.edu/public/problems/13/text

Note:

This problem intuitively resembles a tree structure. But it can be solved using a deque easily, though I think the first data structure that will come to mind is a stack, at least that was in my case. A stack would work, but eventually while accessing all the elements of the stack for length counting, then you will get how deque will serve in that case!

In the following code, there are two limiting criteria:

One is that the length of the level cannot be less than the size of the deque, if it is greater then we have already processed the subdirectory/file and we haven’t found our answer yet, so we can discard that from the deque.

And the second one is the case of checking the virus file. If the virus file is found once, then even if we get our targeted file in the same hierarchy level or in any deeper level of the same root directory, we’ll have to discard it. We have handled this checking using two variables vi and vi_level. One can use 1 variable only instead of these two to check this.

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    string target;
    cin>>target;
    string str,s,ss, ext;
    while(cin>>str)
    {
        s+=str;
        s+="\n";
    }
    int level=0, vi_level=0;
    bool flag=0, vi=0;
    deque<string> dq;

    for(int i=0; i<s.size(); i++)
    {
        if(s[i]=='\n')
        {
            dq.push_back(ss);
            if(flag)
            {
                if(ss==target)
                {
                    cout<<dq[0];
                    for(int i=1; i<dq.size(); i++) cout<<"/"<<dq[i];
                    return 0;
                }
                else if(ext=="virus")
                {
                    vi=1;
                    vi_level=level;
                }
            }
            ss.clear();
            level=0;
            flag=0;
            ext.clear();
        }
        else if(s[i]=='-') level++;
        else if(s[i]=='.')
        {
            if(vi && level>=vi_level) continue;
            ss+=s[i];
            flag=1;
        }
        else
        {
            if(level==0) vi=0;
            if(vi && level>=vi_level) continue;
            ss+=s[i];
            if(flag) ext+=s[i];
            while(level<dq.size()) dq.pop_back();
        }
    }
    return 0;
}

Leave a comment