Common Board| Show all threads Hide all threads Show all messages Hide all messages | | Another approach | andreyDagger | 1134. Cards | 11 Aug 2021 18:10 | 1 | Actually, you can solve it as a graph problem, where numbers 0, 1, ..., n are vertices, which connected like: 0-1, 1-2, ... | | What is correct approach to this problem? | Zergatul | 2127. Determinant of a Graph | 9 Aug 2021 19:16 | 1 | I was able to solve it just by computing matrix determinant. Nothing to do with graphs, just taking advantage of matrix sparsity. | | Some help if you have WA | Amon | 1513. Lemon Tale | 8 Aug 2021 13:09 | 1 | WA #3: 1 1 -> 2 WA #5: 2 1 -> 3 WA #7: 5 3 -> 29 WA #8: 6 5 -> 63 WA #9: 5 1 -> 13 | | WA 2 | Otrebus | 1062. Triathlon | 7 Aug 2021 23:03 | 1 | WA 2 Otrebus 7 Aug 2021 23:03 This is the case of a particularly small competition! | | starting point a is a station but you go by feet | Norbert Nolte | 1205. By the Underground or by Foot? | 7 Aug 2021 07:43 | 4 | If the starting point A is a station but you go by feet, is the station a visited station. For example, what is the solution for the following: 100 101 3 0 0 0 10 1 0 1 2 2 3 0 0 0 0 1 0 | | If you have TL | gaporf | 1198. Jobbery | 7 Aug 2021 06:15 | 3 | If you have TL on test 21, 49 or 50 you should use gets. I get AC with 0.3 s. I was getting TL21, but once I've added "ios_base::sync_with_stdio(false)", I got AC | | Some tests | Otrebus | 1894. Non-Flying Weather | 6 Aug 2021 16:38 | 1 | 3 4 0 2000 1000 3000 0 3000 0 0 3000 0 3000 3000 0 3000 ans: 647.1067811865
5 6 0 2000 500 2500 1000 3000 1500 3000 0 3000 0 0 1500 0 3000 0 1500 0 3000 3000 0 3000 ans: 647.1067811865 3 4 0 0 4000 0 2000 4000 0 0 4000 0 4000 4000 0 4000 ans: 3517.7087639997 4 4 0 0 3000 0 3000 3000 0 3000 2000 2000 5000 2000 5000 5000 2000 5000 ans: 940 4 4 0 0 3000 0 3000 3000 0 3000 1000 1000 -2000 1000 -2000 -2000 1000 -2000 ans: 940 4 3 0 0 30000 0 30000 30000 0 30000 10000 40000 40000 10000 40000 40000 ans: 7011.0678118655 4 4 0 0 3000 0 3000 3000 0 3000 -1000 1000 5000 1000 5000 2000 -1000 2000 ans: 1940 4 4 0 0 3000 0 3000 3000 0 3000 -1000 2000 1000 -1000 2000 -1000 -1000 2000 ans: 647.1067811865 3 3 0 0 4000 2000 0 4000 3000 2000 7000 0 7000 4000 ans: 387.2135955000 Also, WA6 = integer overflow | | WA5. Can anyone help me? | Varduhi Yeghiazaryan | 1096. Get the Right Route Plate! | 6 Aug 2021 05:29 | 4 | Can you give me any hint or any tests? Thanks in advance. I also WA5. When I consider K > 1000, I got AC. The graph is directed i.e. 8 is connected to 5 but 5 is not connected to 8. So that means if the input is 1 8 5 8 5 6 then the answer will be impossible. Edited by author 30.11.2010 02:14 | | For those who dont know how to solve it | Olzhas2dy | 1102. Strange Dialog | 5 Aug 2021 21:55 | 8 | Well, here are some hints: 1. Use DFA. If you do'nt know what it is, visit this page http://en.wikipedia.org/wiki/Deterministic_finite_automaton (pay attention to the table of states) 2. use getc() instead of cin>>ch or cin.getch() or whatever you use (for C++/C only) 3. Try this: 3 outputoutputinputon inputone Edited by author 13.06.2007 17:36I would recommend using gets() for all that want to have the whole string at once. It still is fast enough and does not time limit. How exactly do you use DFS for this? Can you provide an example of some other problem similar to this which is solvable by DFS? Thank you. It's Not DFS problem!!!!! It's DFA(Deterministic finite automaton) problem! I solved it with DFS in 0.453 sec. When I was using STL, I always had TL on the first test but I was sure that this is the correct algo. Then I replaced all STL's strings with array of chars and I got ACC 0.078 . OMGWTF ?! First test is really large. Something of order 1e6. Its a simple substring search problem. | | WA 7??? | mdebvisitor@mail.ru | 1118. Nontrivial Numbers | 4 Aug 2021 15:17 | 1 | WA 7??? mdebvisitor@mail.ru 4 Aug 2021 15:17 I have WA on test 7. What i need to do? | | if you have WA7 | alp | 1118. Nontrivial Numbers | 4 Aug 2021 15:17 | 2 | Output is EndPoint. EndPoint is simple. | | If you WA #3, look at this simple case | jacketinsysu | 1124. Mosaic | 4 Aug 2021 14:09 | 3 | 4 3 1 1 1 2 2 2 3 3 3 4 4 4 > 0 my solution is: edge number + component number - 1. | | if u have WA5 | Rabbit Girl ♥ | 1118. Nontrivial Numbers | 4 Aug 2021 13:54 | 2 | Not work. Can i give my code? | | Test 5??? | mdebvisitor@mail.ru | 1118. Nontrivial Numbers | 4 Aug 2021 13:52 | 1 | Test 5??? mdebvisitor@mail.ru 4 Aug 2021 13:52 What is test 5? I can give my code(It's not working), runtime error(access violation) | | WA #9 | Sergey Kazakov | 2151. Mahjong | 4 Aug 2021 09:14 | 1 | WA #9 Sergey Kazakov 4 Aug 2021 09:14 | | hint solution | mastercopycode | 1471. Distance in the Tree | 4 Aug 2021 01:29 | 1 | you can use Binary Lifting,find lca of u and v you find distance u with root of tree the result=dis[a]+dis[b]-2*dis[lca(a,b)] | | WA on test 8 | Nazmus Sakib | 1471. Distance in the Tree | 4 Aug 2021 01:26 | 2 | No clue as to what's wrong. Can anyone please give me a hint or what's the case? you can show your code , i can help you | | some test cases | Anton | 1017. Staircases | 3 Aug 2021 02:42 | 1 | n = 228 -> ans = 2509198527 n = 121 -> ans = 2368799 n = 10 -> ans = 9 n = 150 -> ans = 19406015 n = 201 -> ans = 517361669 n = 300 -> ans = 114872472063 n = 500 -> ans = 732986521245023 | | WA8 | Kirill | 2104. Game with a Strip | 2 Aug 2021 17:15 | 2 | WA8 Kirill 1 Mar 2020 00:05 I have WA8. Who can help with test? Re: WA8 Sergey Kazakov 2 Aug 2021 17:15 6 ABAAAA AAAAAA -- Alice wins Edited by author 02.08.2021 17:16 | | Help! WA11 | zwqzwq | 1717. Eligibility Rules | 2 Aug 2021 16:57 | 1 | #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; struct dw { ll a,f,s; }A[1600]; bool cmp(dw n1,dw n2) { if(n1.a==n2.a) { if(n1.f==n2.f)return n1.s<n2.s; else return n1.f<n2.f; } else return n1.a<n2.a; } ll ys1[1600],ys2[1600]; ll ans,ad,au,al,ar; struct node { ll l,r,lc,rc,lmax,ln,rmax,rn,mmax,sum,nn; ll L,R,lR,rL; bool have; }tr[3100];ll trlen=0; ll da=1501; void update(ll now) { ll lc=tr[now].lc,rc=tr[now].rc; tr[now].sum=tr[lc].sum+tr[rc].sum; tr[now].nn=tr[lc].nn+tr[rc].nn; ll qwq=-da,ql,qr; if(tr[lc].have){if(tr[lc].mmax>qwq){qwq=tr[lc].mmax;ql=tr[lc].L,qr=tr[lc].R;}} if(tr[rc].have){if(tr[rc].mmax>qwq){qwq=tr[rc].mmax;ql=tr[rc].L,qr=tr[rc].R;}} if(tr[lc].rn+tr[rc].ln>=2){if(tr[lc].rmax+tr[rc].lmax>qwq){qwq=tr[lc].rmax+tr[rc].lmax;ql=tr[lc].rL;qr=tr[rc].lR;}} if(qwq==-da)tr[now].have=false,tr[now].mmax=tr[now].L=tr[now].R=0; else tr[now].have=true,tr[now].mmax=qwq,tr[now].L=ql,tr[now].R=qr; tr[now].lmax=tr[lc].lmax,tr[now].ln=tr[lc].ln,tr[now].lR=tr[lc].lR; if(tr[lc].sum+tr[rc].lmax>=tr[now].lmax)tr[now].lmax=tr[lc].sum+tr[rc].lmax,tr[now].ln=tr[lc].nn+tr[rc].ln,tr[now].lR=tr[rc].lR; tr[now].rmax=tr[rc].rmax,tr[now].rn=tr[rc].rn,tr[now].rL=tr[rc].rL; if(tr[rc].sum+tr[lc].rmax>=tr[now].rmax)tr[now].rmax=tr[rc].sum+tr[lc].rmax,tr[now].rn=tr[rc].nn+tr[lc].rn,tr[now].rL=tr[lc].rL; } void bt(ll l,ll r) { ll now=++trlen;tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1; tr[now].mmax=0;tr[now].have=0;tr[now].lmax=tr[now].rmax=0;tr[now].ln=tr[now].rn=0;tr[now].sum=tr[now].nn=0; tr[now].L=tr[now].R=tr[now].lR=tr[now].rL=0; if(l<r) { ll mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); update(now); } else tr[now].lR=tr[now].rL=l; } void change(ll now,ll x,ll k) { if(tr[now].l==tr[now].r) { tr[now].sum+=k;tr[now].nn++; tr[now].lmax=tr[now].rmax=tr[now].sum; tr[now].ln=tr[now].rn=tr[now].nn; if(tr[now].nn>=2)tr[now].mmax=tr[now].sum,tr[now].L=tr[now].R=x,tr[now].have=true; } else { ll lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; if(x<=mid)change(lc,x,k); else change(rc,x,k); update(now); } } ll n,z1,z2; void solve() { for(ll i=1;i<=n;i++) { trlen=0;bt(1,z2); ll st1=A[i].a,st=i; for(ll j=st1;j<=z1;j++) { bool bk=false; while(st<=n&&A[st].a==j){change(1,A[st].f,A[st].s);st++;bk=1;} if(bk) { if(tr[1].have) { if(ans<tr[1].mmax) { ans=tr[1].mmax; au=st1;ad=j; al=tr[1].L,ar=tr[1].R; } } } } while(i<n&&A[i+1].a==st1)i++; } } struct ls { ll x,id; }AA[1600]; bool cmp1(ls n1,ls n2){return n1.x<n2.x;} int main() { da*=1000000000; scanf("%lld",&n);ll z; for(ll i=1;i<=n;i++)scanf("%lld%lld%lld",&A[i].a,&A[i].f,&A[i].s); for(ll i=1;i<=n;i++)AA[i].x=A[i].a,AA[i].id=i; sort(AA+1,AA+n+1,cmp1);z=0; for(ll i=1;i<=n;i++) { if(i==1||AA[i].x!=AA[i-1].x){z++;ys1[z]=AA[i].x;} A[AA[i].id].a=z; }z1=z; for(ll i=1;i<=n;i++)AA[i].x=A[i].f,AA[i].id=i; sort(AA+1,AA+n+1,cmp1);z=0; for(ll i=1;i<=n;i++) { if(i==1||AA[i].x!=AA[i-1].x){z++;ys2[z]=AA[i].x;} A[AA[i].id].f=z; }z2=z; sort(A+1,A+n+1,cmp); ans=-da;solve(); printf("%lld %lld\n%lld %lld\n",ys1[au],ys1[ad],ys2[al],ys2[ar]); return 0; } |
|
|