Solved it with time of 0.5 sec and using "Trie" where I keep the name of each directory as a node.

only Uzbek from ADHAM!!!
input:

4
TUT\TUT\TUT\TUT\TUT\TUT\TUT
TUT\TUT\BUT\BUT\BUT
BUT\TUT\TUT\TUT\TUT
YUT\YUT\BUT\TUT\YUT

output:

BUT
 TUT
  TUT
   TUT
    TUT
TUT
 TUT
  BUT
   BUT
    BUT
  TUT
   TUT
    TUT
     TUT
      TUT
YUT
 YUT
  BUT
   TUT
    YUT

input:
4
A\A\A\A\A\A\A
A\A\A\A\B\B\B\B
A\A\A\A\C\C\C\CB\B\B\V
A\A\A\A\B\C\C\C\C\C\C

output:

A
 A
  A
   A
    A
     A
      A
    B
     B
      B
       B
     C
      C
       C
        C
         C
          C
    C
     C
      C
       CB
        B
         B
          V

Edited by author 19.06.2013 20:29

Just used STL contaners such as std::map<std::string,T>, std::vector<T>. :)
33 lines of code.

Can someone give me some tests?
I have WA#10, I don't know what else I can fix to solve this problem.
I used hashes, but I think that my simple algorithm can have collisions, because I make hash mod 10000000;
//sorry for my english.
also I changed algorithm, now I don't use mod. But, I still have WA#10.
I used stack + hash, but, all the same

Edited by author 03.12.2012 19:10

Edited by author 03.12.2012 19:34

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
struct node
{
    int old,child,xiong,last;
}tree[200000];
char word[200000][10],s[110];
char w[20];
int how=0;
int child[20000];
int find(int lao,char wo[20])
{
    for (int i=1;i<=how;i++)
        if (strcmp(word[i],wo)==0 && tree[i].old==lao) return i;
    how++;
    strcpy(word[how],wo);
    return how;
}
void qsort(int l,int r)
{
    int i=l,j=r;
    char x[20]="";
    strcpy(x,word[child[(l+r)/2]]);
    do{
        while (strcmp(word[child[i]],x)<0) i++;
        while (strcmp(x,word[child[j]])<0) j--;
        if (i<=j)
        {
            int t=child[i]; child[i]=child[j]; child[j]=t;
            i++; j--;
        }
    }while (i<=j);
    if (i<r) qsort(i,r);
    if (l<j) qsort(l,j);
    return;
}
void search(int kg,int x)
{
    int a[20000];
    if (x!=0)
    {
        for (int i=1;i<=kg;i++) printf(" ");
        printf("%s\n",word[x]);
    }
    memset(a,0,sizeof(a));
    memset(child,0,sizeof(child));
    int y=tree[x].child;
    while (y!=-1)
    {
        a[0]++;
        a[a[0]]=y;
        y=tree[y].xiong;
    }
    for (int i=1;i<=a[0];i++) child[i]=a[i];
    qsort(1,a[0]);
    for (int i=1;i<=a[0];i++) a[i]=child[i];
    for (int i=1;i<=a[0];i++)
        search(kg+1,a[i]);
}
int main()
{
    int t;
    memset(tree,255,sizeof(tree));
    memset(word,0,sizeof(word));
    scanf("%d",&t);
    getchar();
    while (t-->0)
    {
        memset(s,0,sizeof(s));
        gets(s);
        s[strlen(s)]='\\';
        int len=-1,old=0;
        int ss=strlen(s);
        for (int i=0;i<ss;i++)
        {
            if (s[i]!='\\')
            {
                len++;
                w[len]=s[i];
            }
            else if (s[i]=='\\')
            {
               int x;
               x=find(old,w);
               if (old!=-1)
               {
                     if (tree[x].old==-1)
                     {
                         tree[x].old=old;
                         if (tree[old].child==-1) tree[old].child=x;
                         else tree[tree[old].last].xiong=x;
                         tree[old].last=x;
                     }
               }
               old=x;
               len=-1;
               memset(w,0,sizeof(w));
            }
        }
    }
    search(-1,0);
    return 0;
}


Edited by author 06.02.2012 18:42

What is main mistake of programs, which has WA 5?

If you can, write here the hardest or questionable tests, please.

Edited by author 07.02.2011 22:48

#include <cstdlib>
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int n,i,d,j;
string s[505],e[505][90],w,w2,a1,a2;

int main(int argc, char *argv[])
{
   cin>>n;
   for(i=0;i<n;i++)
        cin>>s[i];
   string p;
   p=1;

   w="";
   for(i=0;i<n;i++)
     {
            for(j=0;j<s[i].length();j++)
        if(s[i][j]=='\\')
            s[i][j]=1;
    }
   sort(s,s+n);

    for(i=0;i<n;i++)
        {
            d=0;
            for(j=0;j<s[i].length();j++)
            {w2=s[i][j];
            if(w2.compare(p)==0)
                {
                    d++;

                }
            else
                e[i][d]=e[i][d]+s[i][j];  }
        }
    for(j=0;j<80;j++)
        {if(e[0][j]!="")
            {for(d=0;d<j;d++)
            cout<<" ";

         cout<<e[0][j]<<endl;}

         else
             break;
        }
    for(i=1;i<n;i++)
        {a1="";
         a2="";
            for(j=0;j<80;j++)
                {a1=a1+e[i][j];
                a2=a2+e[i-1][j];

                    if(e[i][j]=="")
                    break;

                else if(a1!=a2)
                {       a1="";
                        a2="";
                        a1=a1+e[i][j];
                        a2=a1+e[i-1][j];
                        for(d=0;d<j;d++)
                        cout<<" ";
                    cout<<e[i][j]<<endl;}
                    }
        }

    return 0;
}

Well,I don't think I often see !~#$%^& in my dictionary...
But I use strcmp directly and it seemed to work.
And a lot of messy structs and pointers made me mad.

I used son-brother to store a tree,so I created a virtual dir called "." in each real dir,that makes programming a bit easier.
Maybe this will somehow help you,or not.

Could someone give me some tests??

First I save the data like that:
f:array[1..500,1..20]of string[8];
It is Wa 10
Next,I change the way:
f:array[1..500,1..100]of string[10];
Then I AC!!!
I hope that can help you!!!

You have to use StringComparer with parameter StringComparison.Ordinal to pass WA7 in CSharp.

I've got AC in this way.

type pver=^tver;
     pe=^te;
     te=record
      e:pe;
      ver:pver;
     end;
     tver=record
      s:string;
      e:pe;
     end;
type trec=record
      s:string;
      ver:pver;
     end;
var i,n:word;
    s:string;
    pb,ver:pver;
    fir:boolean;
procedure add(s:string;ver:pver);
var e:pe;
    vt:pver;
begin
 if s='' then exit;
 e:=ver^.e;
 while e<>nil do begin
  if copy(s,1,pos('\',s)-1)=e^.ver^.s then begin
   delete(s,1,pos('\',s));
   add(s,e^.ver);
   exit;
  end;
  e:=e^.e;
 end;
 new(vt);
 vt^.e:=nil;
 if pos('\',s)>0 then vt^.s:=copy(s,1,pos('\',s)-1) else
 vt^.s:=s;
 new(e);
 e^.ver:=vt;
 e^.e:=ver^.e;
 ver^.e:=e;
 if pos('\',s)>0 then begin
  delete(s,1,pos('\',s));
  add(s,vt);
 end;
end;
procedure writ(ver:pver;ur:word);
var a:array [1..600] of trec;
    t:trec;
    kol,u,i:word;
    e:pe;
begin
 kol:=0;
 e:=ver^.e;
 while e<>nil do begin
  inc(kol);
  a[kol].s:=e^.ver^.s;
  a[kol].ver:=e^.ver;
  e:=e^.e;
 end;
 if kol=0 then exit;
 for u:=1 to kol-1 do
 for i:=1 to kol-u do if a[i].s>a[i+1].s then begin
  t:=a[i];
  a[i]:=a[i+1];
  a[i+1]:=t;
 end;
 for i:=1 to kol do begin
{  if not fir then writeln;
  fir:=false;}
  for u:=1 to ur do write(' ');
  writeln(a[i].s);
  writ(a[i].ver,ur+1);
 end;
end;
begin
 new(pb);
 pb^.e:=nil;
 readln(n);
 for i:=1 to n do begin
  readln(s);
  add(s,pb);
 end;
 fir:=true;
 writ(pb,0);
end.

Can you please say what exactly you mean by "lexicographic order"?
As i can see from neerc.ifmo.ru tests, standart C# comparison doesn't fit; and real used order is not so obvious. So i should know what to implement.
Why NTFS_W98 comes after NTFSDOS?
Why ~INTRO comes after CONTENT?

PS: I think that my code is shortest :p
--
using System;
using System.Collections.Generic;

namespace Task1067 {

    class Directory {

        private Dictionary<string, Directory> SubDirs;

        public Directory() {
            this.SubDirs = new Dictionary<string, Directory>();
        }

        public void ProcessSubdirs(Action<KeyValuePair<string, Directory>> Processor) {
            List<string> Keys = new List<string>(this.SubDirs.Keys);
            Keys.Sort();
            foreach(string Key in Keys) {
                Processor(new KeyValuePair<string, Directory>(Key, this.SubDirs[Key]));
            }
        }

        public void AddDir(Stack<string> DirectoryNames) {
            string Name = DirectoryNames.Pop();
            if(!this.SubDirs.ContainsKey(Name)) this.SubDirs[Name] = new Directory();
            if(DirectoryNames.Count > 0) this.SubDirs[Name].AddDir(DirectoryNames);
        }

    }

    class Program {

        private static void PrintSubdirs(Directory Dir, int Depth) {
            Dir.ProcessSubdirs(delegate(KeyValuePair<string, Directory> kvp) {
                Console.WriteLine(new String(' ', Depth) + kvp.Key);
                PrintSubdirs(kvp.Value, Depth+1);
            });
        }

        static void Main(string[] args) {

            int Count = int.Parse(Console.ReadLine());
            Directory RootDir = new Directory();
            for(int i=0; i<Count; i++) {
                List<string> PathComponents = new List<string>(Console.ReadLine().Trim().Split('\\'));
                PathComponents.Reverse();
                RootDir.AddDir(new Stack<string>(PathComponents));
            }

            PrintSubdirs(RootDir, 0);
        }
    }
}

I get CE. Why?

#include <iostream>
#include <vector>
#include <sstream>
#include <set>
using namespace std;

template < class TypeTree > class less_of_tree
{
public :
________bool operator () (TypeTree a, TypeTree b)
________{
________________return a.name < b.name;
________}
};

class tree
{
public :
________string name;
________set < tree, less_of_tree < tree > > child;

________tree ();
________tree (string s);
________void add (int x, vector < string > way);
________void print (string row);
};
...

e:\judge\Judge\Vc7\include\xtree(988): error: no instance of function "less_of_tree<TypeTree>::operator() [with TypeTree=tree]" matches the argument list and object (the object has cv-qualifiers that prevent a match)
            argument types are: (const tree, const std::_Tree<std::_Tset_traits<tree, less_of_tree<tree>, std::allocator<tree>, false>>::key_type)
            object type is: const less_of_tree<tree>
     if (this->comp(_Key(_Pnode), _Keyval))

         ^
          detected during:
            instantiation of "std::_Tree<_Traits>::_Nodeptr std::_Tree<_Traits>::_Lbound(const std::_Tree<_Traits>::key_type &) const [with _Traits=std::_Tset_traits<tree, less_of_tree<tree>, std::allocator<tree>, false>]" at line 801
            instantiation of "std::_Tree<_Traits>::iterator std::_Tree<_Traits>::lower_bound(const std::_Tree<_Traits>::key_type &) [with _Traits=std::_Tset_traits<tree, less_of_tree<tree>, std::allocator<tree>, false>]" at line 779
            instantiation of "std::_Tree<_Traits>::iterator std::_Tree<_Traits>::find(const std::_Tree<_Traits>::key_type &) [with _Traits=std::_Tset_traits<tree, less_of_tree<tree>, std::allocator<tree>, false>]" at line 50 of "43d08e8e-4606-476a-85b3-38e5b7230ae9"

Edited by author 10.05.2008 18:42

My solution is written in Java, and it fails on the 1st test.
However, it passes all from NEERC site and all I've found in other topics.
I think the problem is out of algorithm, but I can't even guess what it can be... :(
Can anyone please give me a piece of advice?

My program works well on my own computer with Free Pascal IDE 2.2.0. But when I submitted it, it got 'Compilation error'. I'm really confused. Could someone help me? Thanks.

input#1:

3
a\b\c
a\b\c
b

output#1:

a
_b
__c
b

input#2:
9
a
a\b
a\b\c
a\b\c
a\b\c\d
b\f
b\f\e
b\f\d
b\e

output#2:

a
_b
__c
___d
b
_e
_f
__d
__e

input#3:
3
a
a\b\c\d\e\f
a\b\r\t\p

output#3:
a
_b
__c
___d
____e
_____f
__r
___t
____p

input#4:
4
a\b
b\a
a\c\d
a\c\e

output#4:
a
_b
_c
__d
__e
b
_a


input#5:
4
a
a\b\c\d\e
b\f\e\t
a\b\p

output#5:
a
_b
__c
___d
____e
__p
b
_f
__e
___t

Edited by author 01.10.2007 23:38

Edited by author 01.10.2007 23:42

Edited by author 01.10.2007 23:46

type
str = string;
var
  a:array[1..500] of str;
  i,j,n,t,p,f,l:integer;
  s:str;
function sort(t1,t2:integer):boolean;
var
i,n:integer;
begin
i:=0;
sort:=false;
if length(a[t1])>length(a[t2]) then n:=length(a[t2]) else n:=length(a[t1]);
while i<n  do
   begin
   inc(i);
   if ((a[t1][i]>a[t2][i]) and ((a[t1][i]<>'\') and (a[t2][i]<>'\')))
   or ((a[t2][i]='\') and (a[t1][i]<>'\')) then
        begin
          s:=a[t1];
          a[t1]:=a[t2];
          a[t2]:=s;
          i:=n;
          sort:=true;
        end else
   if (a[t1][i]<a[t2][i]) or ((a[t1][i]='\') and (a[t2][i]<>'\')) then i:=n
   end;
end;
procedure kor(k:str; z:integer);
var
i:integer;
begin
   t:=1;
   for i:=1 to length(k) do
   if k[i]='\' then
     begin
      s:=copy(k,t,i-t);
      t:=i+1;
      writeln(s:(length(s)+z));
      inc(z);
     end;
end;
begin
{   assign(input,'c:\test.txt'); reset(input);}
   readln(n);
   for i:=1 to n do begin readln(a[i]); a[i]:=a[i]+'\'; end;
   i:=0;
   while i<n-1 do
   begin
    inc(i);
    if sort(i,i+1) then i:=0;
   end;
   kor(a[1],0);
   for i:=2 to n do
     begin
       t:=0; f:=0;
       if length(a[i-1])<length(a[i]) then l:=length(a[i]) else l:=length(a[i-1]);
       for j:=1 to l do
         if a[i][j]<>a[i-1][j] then break
         else if a[i][j]='\' then begin t:=j; inc(f); end;
       s:=a[i];
       if t=0 then kor(s,t) else begin  delete(s,1,t); kor(s,f); end;
     end;
 {  close(input);}
end.

and if i change str = string => str = string[90] i have wa5?!!!!

Anybody know why?

I use this structure for save tree.

struct node{
    char *name;
    node *next;
    node *subfolder;
};
sizeof(node)=12;
for ten test a have 20000*12=420 Kb for node
and 40*50*(2-3)=50 Kb for names
total 500 Kb, but I Get MLE with memory=1500 Kb
Maybe my recurse function use many memory?
Sorry for my English.

Edited by author 18.04.2005 12:46