Show all threads Hide all threads Show all messages Hide all messages | Accepted 0.156 2 993 КБ | TakeOver | 1067. Disk Tree | 29 Dec 2022 02:14 | 3 | 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 | wa 5 | 👑TIMOFEY👑 | 1067. Disk Tree | 2 Nov 2022 10:21 | 1 | wa 5 👑TIMOFEY👑 2 Nov 2022 10:21 i think its something like this 2 ab\df\fd df\df ab df fd df df fd | Everybody who get confused on this problem should look at this!! | Drayd | 1067. Disk Tree | 28 Feb 2019 08:50 | 4 | 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 | Hint for WA#1 | ruX | 1067. Disk Tree | 2 Sep 2018 23:11 | 1 | Make sure you don't have spaces after any line | If you have WA5 | tproger | 1067. Disk Tree | 4 Mar 2018 23:08 | 1 | 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! ;) | I have WA8. Please check my tests and add your tests | <-UnderFelixAbove-> | 1067. Disk Tree | 1 Jan 2018 14:48 | 5 | 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 | My code crashed at 10th test | Rabbit Girl ♥ | 1067. Disk Tree | 6 Dec 2017 20:58 | 1 | 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! | WA7 in C# | ₰ҟᾷ®ßὂνṑγ (ONPU) | 1067. Disk Tree | 28 Apr 2015 22:35 | 4 | You have to use StringComparer with parameter StringComparison.Ordinal to pass WA7 in CSharp. I've got AC in this way. | Nice problem :) | Radoslav Dimitrov | 1067. Disk Tree | 11 Mar 2015 01:22 | 1 | Solved it with time of 0.5 sec and using "Trie" where I keep the name of each directory as a node. | 5-testga xato qilganlar uchun 2 ta example | Adhambek | 1067. Disk Tree | 20 Jun 2013 12:53 | 2 | 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 | WA #10 | TakeOver | 1067. Disk Tree | 3 Dec 2012 13:31 | 1 | WA #10 TakeOver 3 Dec 2012 13:31 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 | Help! Crash (stack overflow) on TEST 10 | Exia | 1067. Disk Tree | 6 Feb 2012 18:37 | 1 | #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 | If input like this , what will output like ? | lyj_george | 1067. Disk Tree | 31 Jan 2012 06:30 | 7 | 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. | WA 5 | Muravjev Slava [Samara SAU] | 1067. Disk Tree | 7 Feb 2011 22:46 | 1 | WA 5 Muravjev Slava [Samara SAU] 7 Feb 2011 22:46 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 | Why wrong answer5?????? See my code. | Programmer | 1067. Disk Tree | 23 Jul 2010 16:55 | 3 | 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 | What is wrong test 5 | QAFQAZ.Alekber.Velizade | 1067. Disk Tree | 6 Jun 2010 20:26 | 4 | #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? | lexicographic order ? | tiancaihb | 1067. Disk Tree | 13 Aug 2009 11:58 | 1 | 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. | Wa10 Come in,I hope I can solve your problem | Rabidstorm | 1067. Disk Tree | 23 May 2009 10:29 | 2 | 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 ... | WA6,HELP!!! | yangqiang | 1067. Disk Tree | 9 Apr 2009 06:49 | 1 | Could someone give me some tests?? | The subdirectories shall be listed in lexicographic order | penartur | 1067. Disk Tree | 20 Oct 2008 01:12 | 2 | 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); } } } |
|
|