Show all threads Hide all threads Show all messages Hide all messages | accepted | Mikhail | 1210. Kind Spirits | 11 Nov 2019 03:59 | 2 | //#pragma GCC optimize("Ofast,no-stack-protector") //#pragma GCC target("avx") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds; using namespace std;
#define re return #define pb push_back #define eb emplace_back #define all(x) (x).begin(), (x).end() #define fi first #define se second #define sqrt(x) sqrt(abs(x)) #define mp make_pair #define pi (3.14159265358979323846264338327950288419716939937510) #define fo(i, n) for(int i = 0; i < n; ++i) #define ro(i, n) for(int i = n - 1; i >= 0; --i) #define unique(v) v.resize(unique(all(v)) - v.begin())
template <class T> T abs (T x) { re x > 0 ? x : -x; } template <class T> T sqr (T x) { re x * x; } template <class T> T gcd (T a, T b) { re a ? gcd (b % a, a) : b; } template <class T> int sgn (T x) { re x > 0 ? 1 : (x < 0 ? -1 : 0); }
typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<string> vs; typedef double D; typedef long double ld; typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vll; typedef unsigned long long ull; typedef tree <pair<int, char>, null_type, less<pair<int, char>>, rb_tree_tag, tree_order_statistics_node_update> _tree; const int maxn = 31; vector <pair<int, ii>> g[maxn][maxn]; int d[maxn][maxn]; bool _sort(ii a, ii b) { if (d[a.fi][a.se] != d[b.fi][b.se]) re d[a.fi][a.se] < d[b.fi][b.se]; re a < b; } set <ii, bool (*) (ii, ii)> s(_sort); void read (int a, int b) { int k, x, w; cin >> k; fo(i, k) { cin >> x; while (x != 0) { cin >> w ; g[a][x - 1].pb(mp(b, mp(i, w))); cin >> x; } } } void dejkstra() { fo(i, maxn) fo(j, maxn) d[i][j] = (int) 1e9; d[0][0] = 0; int x, y, a, b, w; s.insert(mp(0, 0)); while (!s.empty()) { x = (*s.begin()).fi, y = (*s.begin()).se; s.erase(s.begin()); for (auto &j : g[x][y]) { a = j.fi, b = j.se.fi, w = j.se.se; if (d[a][b] > d[x][y] + w) { s.erase(mp(a, b)); d[a][b] = d[x][y] + w; s.insert(mp(a, b)); } } } } int main() { int n; cin >> n; string str; for (int i = 1; i <= n; ++i) { read (i - 1, i); if (i < n) cin >> str; } dejkstra(); int ans = (int) 1e9; fo(i, maxn) ans = min(ans, d[n][i]); cout << ans << endl; } #include <iostream> #include <vector> #include <cmath> using namespace std; int main() { int n; cin >> n; // quantity of levels in Ivans map int cs[35][35][35]; vector<int> v[35][35]; int inLevel[35]; for(int i = 1; i <= n; ++i) { int k; cin >> k; inLevel[i] = k; for(int j = 1; j <= k; ++j) { while(true) { int a, b; cin >> a; if(a == 0) { break; } cin >> b; v[i][j].push_back(a); /// on i-th level to planet "j" we can come from planet "a" in i-1 - th level cs[i][j][a] = b; /// on i-1-th level planet "a" pay b$ for going to planet "j" in i-th - level } } if(i == n) break; char x; cin >> x; } int dist[35][35]; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= inLevel[i]; ++j) { dist[i][j] = 10010010; } } dist[0][1] = 0; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= inLevel[i]; ++j) { for(int k = 0; k < v[i][j].size(); ++k) { int pl = v[i][j][k]; if(dist[i][j] > dist[i-1][pl] + cs[i][j][pl]) { dist[i][j] = dist[i-1][pl] + cs[i][j][pl]; } } } } int mn = 10010020; for(int i = 1; i <= inLevel[n]; ++i) { mn = min(mn, dist[n][i]); } cout << mn; } sorry for my terrible english Edited by author 11.11.2019 04:02 | Wrong constraint for test case #9 | cylau1996 | 1210. Kind Spirits | 15 Sep 2019 10:01 | 1 | The question stated that 0 < N < 30. However, in test case #9 N is exactly 30, contradicting the constraint. | WA #9 Useful Test | SergeyGlazkov [SPbPU] | 1210. Kind Spirits | 25 Jul 2019 06:56 | 1 | If you have WA #9 try this: 4 1 1 32300 0 * 1 1 32300 0 * 1 1 32300 0 * 1 1 32300 0 answer: 129200 | WA #5. Some tests is needed | Rakovets Alex | 1210. Kind Spirits | 23 Feb 2019 11:58 | 6 | I`m sure that written algo is correct, but I might make stupid mistake... My solutions can pass all my tests and my friends` also. Please, give me some tricky tests! Thanks a lot! 2 2 0 1 2 0 * 2 1 1 0 2 3 0 answer 5 Here are some tests: TEST : 10 1 1 10 0 * 1 1 10 0 * 1 1 10 0 * 1 1 10 0 * 1 1 10 0 * 1 1 10 0 * 1 1 10 0 * 1 1 10 0 * 1 1 10 0 * 1 1 10 0 answer 100 TEST: 1 3 1 10 0 2 -5 0 3 -1000 0 answer -1000 Here are some tests: TEST: 1 3 1 10 0 2 -5 0 3 -1000 0 answer -1000 I think this test is wrong, because we have only 1 planet on the 0th level, So it should be: 1 3 1 10 0 1 -5 0 1 -1000 0 | WA #9 | Sunkyu Hwang | 1210. Kind Spirits | 23 Feb 2019 11:57 | 3 | WA #9 Sunkyu Hwang 20 Feb 2017 10:47 I keep getting non-zero return from WA #9 (meaning some of my scanf() fails) Could you please forward WA #9 problem so that I can check parsing is proper? Thank you, Re: WA #9 Kondarattcev Denis [Ufa] 3 Nov 2017 19:18 Test #9 probably contains upper limit case, when there are max possible levels with max planets in each, I can suggest you to check your array sizes. I also got WA #9 after setting wrong integer value for "unreachable" planets - I've set it too small and it affected the result at this test You're right... After changing the values to a higher value for the unreachable nodes, I got AC. Thanks. | if wa2 | tishinilia | 1210. Kind Spirits | 1 Sep 2018 16:53 | 1 | if wa2 tishinilia 1 Sep 2018 16:53 use max=10**9 maybe, i'm just silly | More test cases | azikar24 | 1210. Kind Spirits | 20 Feb 2018 00:09 | 1 | Make sure your graph is more than 1296 and try these 3 2 1 2 0 1 5 0 * 3 1 8 2 3 0 1 -5 0 2 25 0 * 2 1 8 2 22 3 -15 0 2 19 3 -50 0 ans = -20 =========================== 4 2 1 2 0 1 5 0 * 4 1 8 2 3 0 1 -5 0 2 25 0 1 22 2 -3 0 * 3 1 8 2 22 3 -15 0 2 19 3 -50 0 4 -1 2 -5 0 * 4 1 -8 2 18 0 1 -5 0 2 -19 3 -22 0 1 12 0 ans= -39 ============================== 2 2 1 2 0 1 5 0 * 4 1 8 2 3 0 1 -5 0 2 25 0 1 22 2 -3 0 ans = -3 ========================== 4 2 1 2 0 1 5 0 * 4 1 81 2 23 0 1 56 0 2 25 0 1 22 2 -31 0 * 3 1 8 2 22 3 -15 0 2 19 3 -50 0 4 -1 2 -5 0 * 4 1 82 2 18 0 1 59 0 2 39 3 52 0 1 112 0 ans = -2 | WA,What's wrong with my program? Please HELP! THANKS! | Nico | 1210. Kind Spirits | 25 Aug 2015 16:00 | 4 | #include <iostream> #include <vector> using namespace std; const int MAXVALUE=999999999; int MinInVector(std::vector<int> v); class Kind_Spirits { public: Kind_Spirits(int); void ReadCompute();
private: int BlockNumber,Level; std::vector<vector<int> > DistanceLevel; }; int main(int argc, char const *argv[]) { //cout<<"MAXVALUE= "<<MAXVALUE; int a; cin>>a; Kind_Spirits* KS = new Kind_Spirits(a); KS->ReadCompute(); return 0; } Kind_Spirits::Kind_Spirits(int n) { BlockNumber=n; Level=0; std::vector<int> tv; DistanceLevel.resize(n+1,tv); DistanceLevel[0].push_back(0); } void Kind_Spirits::ReadCompute() { char LevelNumber; int NO,dis,bn=BlockNumber; while(bn--) { cin>>LevelNumber; if(LevelNumber=='*') { bn++; continue; } Level++; for(int i=0;i<(int)LevelNumber-48;i++) { DistanceLevel[Level].resize((int)LevelNumber-48,MAXVALUE); while(cin>>NO&&NO!=0) { cin>>dis; DistanceLevel[Level][i]= min(DistanceLevel[Level][i],DistanceLevel[Level-1][NO-1]+dis); } //cout<<"Level min"<<DistanceLevel[Level][i]<<endl; } } //for(int i=0;i<BlockNumber+1;i++) //dspv(DistanceLevel[i]); cout<<MinInVector(DistanceLevel[BlockNumber])<<endl; } int MinInVector(std::vector<int> v) { int m=MAXVALUE; for(unsigned int i=0;i<v.size();i++) { m=min(m,v[i]); } return m; } Edited by author 25.08.2015 14:47 Edited by author 25.08.2015 14:54 Edited by author 25.08.2015 14:54 Who can give me some tricky test! Thank you very much! | I think that it seems to be dp problem) | Alibi | 1210. Kind Spirits | 23 May 2015 07:34 | 2 | | WA 5 :( | esraa.ali | 1210. Kind Spirits | 15 Sep 2014 05:41 | 1 | WA 5 :( esraa.ali 15 Sep 2014 05:41 can i have test 5 please I`m sure that my solution is correct, but I have WA on 5 test... My solutions can pass all the tests shown Please, give me test 5 ,or some tricky tests! Thanks a lot! | For whom, who get WA 6 | Gleb_Kazantaev(NNSTU) | 1210. Kind Spirits | 22 Jul 2014 19:25 | 1 | If u used Dijkstra alg, u should add min price for all pices, and theh deduct it from unswer multiplying on count of the tops. Sorry for my eng :D | WA #7 | chickenway | 1210. Kind Spirits | 6 Dec 2013 08:41 | 1 | WA #7 chickenway 6 Dec 2013 08:41 I'm wrong with test 7, can someone give me some test? Thanks. Edited by author 06.12.2013 09:29 Edited by author 06.12.2013 09:29 | I agree with last orators, can somebody give #6 test? | AndrKonin | 1210. Kind Spirits | 16 Sep 2013 16:53 | 1 | | WA on 6 test | R. Dubinin | 1210. Kind Spirits | 29 Jul 2013 23:51 | 1 | please, give me some tests. | W.A. on the 6 test!!!! | Ivan | 1210. Kind Spirits | 16 Jul 2013 17:55 | 2 | Give me sixth test, please!!! i also have WA on 6 test, please, give me some tests. | So what is test 6? - Runtime Error with C# | NeoTheFox | 1210. Kind Spirits | 3 Apr 2013 16:46 | 1 | I dont know if it is my mistake or difference between Mono and Microsoft C#, but it fails at test 6 with runtime error. Is there a way I can know what test 6 is? | For the people who WA TEST#5 | bobchennan | 1210. Kind Spirits | 8 Apr 2011 17:12 | 3 | #include <stdio.h> int main() { long i,a[2][100]={0},n,k,x,y,j,c=0,next; long max=2147483647; char ch; scanf("%ld*",&n); for (i=1;i<=n;i++) { scanf("%ld*",&k); for (j=1;j<=k;j++) a[c][j]=2147483647; next=(c+1)%2; for (j=1;j<=k;j++) { scanf("%ld",&x); while (x!=0) { scanf("%ld*",&y); if (a[c][j]>a[next][x]+y) a[c][j]=a[next][x]+y; scanf("%ld",&x); } } if (i!=n) { c=next; scanf("%c*",&ch); } } for (i=1;i<=k;i++) if (a[c][i]<max) max=a[c][i]; printf("%ld",max); return 0; }
Initial value0-------> Initial value2147483647 I think TEST#5 must have a node which min value is 0. in TEST#5 is a Nth level planet which can not go with the Ivanushka's planet #include "iostream" using namespace std; void main () { long n,lay,from,fee; long i=0; long j; long arr[35]; long arr2[35]; long* one; long* two; long* help; char c; for (i=0;i<35;i++) { arr2[i]=0; arr[i]=0; }; one=arr; two=arr2; cin>>n; for (i=0;i<n;i++) { cin>>lay; for (j=0;j<lay;j++) { cin>>from; if (from==0) { continue;} cin>>fee; two[j+1]=one[from]+fee; while(2>1) { cin>>from; if (from==0) { break;} cin>>fee; if (two[j+1]>(one[from]+fee)) { two[j+1]=one[from]+fee; }; }; }; if (i!=n-1) { help=one; one=two; two=help; cin>>c; }; }; long m; m=two[1]; for (j=1;j<lay;j++) if (m>two[j+1]) m=two[j+1]; cout<<m; } | AC 0.093 143 Kb | Виктор Крупко | 1210. Kind Spirits | 8 Apr 2011 17:12 | 9 | Whether it is possible better? 0.015 166 КБ :D See I have you write down if you want to know how it can be :D 0.015 132 Kb - now by changing longint to integer :D #include "iostream" using namespace std; void main () { long n,lay,from,fee; long i=0; long j; long arr[35]; long arr2[35]; long* one; long* two; long* help; char c; for (i=0;i<35;i++) { arr2[i]=0; arr[i]=0; }; one=arr; two=arr2; cin>>n; for (i=0;i<n;i++) { cin>>lay; for (j=0;j<lay;j++) { cin>>from; if (from==0) { continue;} cin>>fee; two[j+1]=one[from]+fee; while(2>1) { cin>>from; if (from==0) { break;} cin>>fee; if (two[j+1]>(one[from]+fee)) { two[j+1]=one[from]+fee; }; }; }; if (i!=n-1) { help=one; one=two; two=help; cin>>c; }; }; long m; m=two[1]; for (j=1;j<lay;j++) if (m>two[j+1]) m=two[j+1]; cout<<m; } | Give me some tests | Duzhy Igor | 1210. Kind Spirits | 31 Dec 2009 23:43 | 3 | I think that my program is correct, but i don't understand why i have WA#5. I use Dejkstra algorithm. Please, give me some right tests. Than I use another method - DP. I use 2 arrays for the current and previous states, but I have WA#7. Help!!! Thanks. Edited by author 06.10.2006 22:31 Edited by author 06.10.2006 22:31 Edited by author 06.10.2006 22:31 As i know - Dejkstra dosn't work for graph with negative weight of edge. 3 2 1 15 0 1 5 0 * 4 1 -5 2 10 0 1 3 0 2 40 0 0 * 3 1 1 2 5 3 -5 0 2 -19 3 -20 0 4 -100 0 Answer is -1 | why WA test#4 please Help me!!!!!!! | hisp | 1210. Kind Spirits | 30 Oct 2009 17:13 | 1 | Why WA test#4 please Help me!!!!!!! I used Deikstra and floida |
|
|