Just used STL contaners such as std::map<std::string,T>, std::vector<T>. :) 33 lines of code. what is "T"? give please full description. I used a map and a set. My time was a little less than 2 times faster, and used a little more than 2 times more memory. struct dir { std::string name; std::map<std::string, dir*> children_items; std::set<std::string> children_names; }; The set gives you the sorted list. The map gives you instant access to a subdirectory of a given directory by name (taken from the set) Edited by author 29.12.2022 02:15 i think its something like this 2 ab\df\fd df\df ab df fd df df fd just consider this condiction: 2 A\A B\A the correct output is A A B A but if you are mistaken, you will output A A Of course, folders on different depths (or in different subtrees) can have equal names. (look at disk tree on your computer). Edited by author 30.10.2004 22:38 Why couldn't it be : B A A ?? All the given directory addresses start from same common root Make sure you don't have spaces after any line If you use set<A*> or std::sort/std::stable_sort vector/array of pointers, your comparator won't work, because you need special comparator, like this struct APtrCmp { bool operator()(const A* lhs, const A* rhs) const { /* implement logic here */ } }; set<A*, APtrCmp> yourSet; Good luck! ;) 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 Yeah, your tests are absolutelly correct... caz my AC solution has the same outputs.... try this test 1 ab\c\d\e my be it'll help... 4 a\baba a\bab a\babab a\bab\ba a bab ba baba babab MR.qo`y yaxshiroq test yoz thank you very much for the tests I implemented a prefix tree using pointers and it crashed. I don't know why : for me it worked at max test. But as soon as I moved to an array implementation, it worked! You have to use StringComparer with parameter StringComparison.Ordinal to pass WA7 in CSharp. I've got AC in this way. 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 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 INPUT: a\b d\a cc\e e\d OTHERWISE,does it have any special situations ? The output should be: a b cc e d a e d I don't think so. But you should take care not to repeat entries, like in this situation: input: a/b a output: a b and NOT: a b a type Ttree=^atree; atree=record name:string; son:Ttree; same:Ttree; end; var tree:Ttree; i,j,k,n:integer; p:Ttree; s:string; procedure create(s:string;var p:Ttree); var t,q:ttree; ss:string; begin if s='' then exit; new(q);q^.name:=''; q^.same:=nil; q^.son:=nil; ss:=copy(s,1,pos('\',s)-1); delete(s,1,pos('\',s)); if p=nil then begin q^.name:=ss; create(s,q^.son); p:=q; p^.same:=p; end else begin t:=p; while (p^.name<ss)and(p^.same<>t)and(p^.same^.name<=ss) do p:=p^.same; if p^.name=ss then create(s,p^.son) else begin q^.name:=ss; create(s,q^.son); q^.same:=p^.same; p^.same:=q; end; end; while p^.same^.name>p^.name do p:=p^.same; while p^.same^.name<p^.name do p:=p^.same; end; procedure print(i:integer;q:Ttree); var t:ttree; begin t:=q; repeat writeln(' ':i+1,q^.name); if q^.son<>nil then print(i+1,q^.son); q:=q^.same; until q=t; end; begin tree:=nil; readln(n); for i:=1 to n do begin readln(s); create(s+'\',tree); end; print(0,tree); end. Program disktree; const max=500; var a:array[1..max] of string[100]; n:integer; procedure init; var i,j:integer; begin readln(n); for i:=1 to n do begin readln(a[i]); for j:=1 to length(a[i]) do if a[i,j]='\' then a[i,j]:=#1; end; end; procedure mendheap(i,now:integer); var t:integer; st:string[80]; begin while i shl 1<=now do begin if i shl 1=now then t:=now else if a[i shl 1]>a[i shl 1+1] then t:=i shl 1 else t:=i shl 1+1; if a[i]<a[t] then begin st:=a[i]; a[i]:=a[t]; a[t]:=st; i:=t; end else i:=now; end; end; procedure dothing; var i:integer; st:string[80]; begin for i:=n shr 1 downto 1 do mendheap(i,n); for i:=n-1 downto 2 do begin st:=a[1]; a[1]:=a[i+1]; a[i+1]:=st; mendheap(1,i); end; st:=a[1]; a[1]:=a[2]; a[2]:=st; end; procedure print; var i,j,t,t1:integer; s,s1,s2,st:string; begin s:=#0#0; for i:=1 to n do begin st:=a[i]; if s=copy(st,1,length(s)) then begin t:=1; for j:=1 to length(s) do if s[j]=#1 then inc(t); end else begin j:=1; t:=0; while st[j]=s[j] do begin if st[j]=#1 then inc(t); inc(j); end; end; j:=1; t1:=t; while t1>0 do begin if st[j]=#1 then dec(t1); inc(j); end; s:=st; st:=st+#1; delete(st,1,j-1); while st>'' do begin if t>0 then write(' ':t); j:=pos(#1,st); writeln(copy(st,1,j-1)); inc(t); delete(st,1,j); end; end; end; Begin init; dothing; print; End. 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 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. This test help me. 2 GAMES\GGG GAMES #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; } I find your mistake.You used c++.You must use delphi.ok? 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. 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!!! f[1..500,1..80] is enough. But I still WA on #8 ... Could someone give me some tests?? 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); } } } |
|