답안 #61235 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61235	2018-07-25T11:55:13 Z	dukati8	Fireworks (APIO16_fireworks)	C++14	26 / 100	39 ms	1660 KB

fireworks

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i=a; i<int(b); i++)

int main() {
  int n,m;
  cin >> n >> m;
  vector<int>p(n+m);
  vector<long long>c(n+m);
  p[0]=-1;
  c[0]=-1;
  rep (i,1,n+m) {
    cin >> p[i] >> c[i];
    p[i]--; //0-indexed
  }
  if (n==1 && m<=100) {
    rep (i,1,m+1) {
      assert(p[i]==0);
    }
    sort(c.begin(),c.end());
    long long goal=c[m/2+1];
    long long ans=0;
    rep (i,1,m+1) {
      ans+=abs(goal-c[i]);
    }
    cout << ans << endl;
  }
  else {
    //assume N+M <=300 and longest path <=300;
    long long cost[n+m][301]; //This will be, for every node, cost[t] is cost to make that node a certain time t
    vector<vector<int> > children (n);
    rep (i,1,n+m) {
      children[p[i]].push_back(i);
    }
    queue<int> ready;
    int done[n]; //Says how many of intersection i's children are done
    rep (i,0,n) done[i]=0;
    rep (i,n,n+m) {
      //Loop over all leafs, set costs
      cost[i][0]=0; //All leafs are 0
      rep (j,1,301) {
        cost[i][j]=999999999;
      }
      done[p[i]]++;
      if (done[p[i]]==children[p[i]].size()) {
        ready.push(p[i]);
      }
    }
    while (true) {
      int curr =ready.front();
      ready.pop();
      rep (i,0,301) {
        cost[curr][i]=0;
        //calculate sum for all children
        for (auto child:children[curr]) {
          long long best=999999999;
          rep (j,0,i+1) {
            best=min(best,cost[child][j]+abs(i-j-c[child]));
          }
          cost[curr][i]+=best;
        }
      }
      if (curr==0) break;
      done[p[curr]]++;
      if (done[p[curr]]==children[p[curr]].size()) ready.push(p[curr]);
    }
    long long best=999999999;
    rep (i,0,301) {
      best=min(best,cost[0][i]);
    }
    cout << best << endl;

  }
}

Compilation message

fireworks.cpp: In function 'int main()':
fireworks.cpp:46:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (done[p[i]]==children[p[i]].size()) {
           ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fireworks.cpp:66:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (done[p[curr]]==children[p[curr]].size()) ready.push(p[curr]);
           ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	3 ms	524 KB	Output is correct
4	Correct	3 ms	584 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	584 KB	Output is correct
7	Correct	4 ms	584 KB	Output is correct
8	Correct	4 ms	584 KB	Output is correct
9	Correct	3 ms	584 KB	Output is correct
10	Correct	3 ms	584 KB	Output is correct

Subtask #2
19.0 / 19.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	584 KB	Output is correct
2	Correct	5 ms	584 KB	Output is correct
3	Correct	9 ms	704 KB	Output is correct
4	Correct	14 ms	704 KB	Output is correct
5	Correct	19 ms	832 KB	Output is correct
6	Correct	13 ms	832 KB	Output is correct
7	Correct	14 ms	876 KB	Output is correct
8	Correct	15 ms	1020 KB	Output is correct
9	Correct	16 ms	1020 KB	Output is correct
10	Correct	24 ms	1020 KB	Output is correct
11	Correct	32 ms	1152 KB	Output is correct
12	Correct	28 ms	1152 KB	Output is correct
13	Correct	23 ms	1152 KB	Output is correct
14	Correct	28 ms	1404 KB	Output is correct
15	Correct	27 ms	1404 KB	Output is correct
16	Correct	27 ms	1404 KB	Output is correct
17	Correct	26 ms	1404 KB	Output is correct
18	Correct	31 ms	1404 KB	Output is correct
19	Correct	38 ms	1404 KB	Output is correct

Subtask #3
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	3 ms	524 KB	Output is correct
4	Correct	3 ms	584 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	584 KB	Output is correct
7	Correct	4 ms	584 KB	Output is correct
8	Correct	4 ms	584 KB	Output is correct
9	Correct	3 ms	584 KB	Output is correct
10	Correct	3 ms	584 KB	Output is correct
11	Correct	3 ms	584 KB	Output is correct
12	Correct	5 ms	584 KB	Output is correct
13	Correct	9 ms	704 KB	Output is correct
14	Correct	14 ms	704 KB	Output is correct
15	Correct	19 ms	832 KB	Output is correct
16	Correct	13 ms	832 KB	Output is correct
17	Correct	14 ms	876 KB	Output is correct
18	Correct	15 ms	1020 KB	Output is correct
19	Correct	16 ms	1020 KB	Output is correct
20	Correct	24 ms	1020 KB	Output is correct
21	Correct	32 ms	1152 KB	Output is correct
22	Correct	28 ms	1152 KB	Output is correct
23	Correct	23 ms	1152 KB	Output is correct
24	Correct	28 ms	1404 KB	Output is correct
25	Correct	27 ms	1404 KB	Output is correct
26	Correct	27 ms	1404 KB	Output is correct
27	Correct	26 ms	1404 KB	Output is correct
28	Correct	31 ms	1404 KB	Output is correct
29	Correct	38 ms	1404 KB	Output is correct
30	Incorrect	39 ms	1660 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #4
0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	376 KB	Output is correct
2	Correct	3 ms	484 KB	Output is correct
3	Correct	3 ms	524 KB	Output is correct
4	Correct	3 ms	584 KB	Output is correct
5	Correct	4 ms	584 KB	Output is correct
6	Correct	4 ms	584 KB	Output is correct
7	Correct	4 ms	584 KB	Output is correct
8	Correct	4 ms	584 KB	Output is correct
9	Correct	3 ms	584 KB	Output is correct
10	Correct	3 ms	584 KB	Output is correct
11	Correct	3 ms	584 KB	Output is correct
12	Correct	5 ms	584 KB	Output is correct
13	Correct	9 ms	704 KB	Output is correct
14	Correct	14 ms	704 KB	Output is correct
15	Correct	19 ms	832 KB	Output is correct
16	Correct	13 ms	832 KB	Output is correct
17	Correct	14 ms	876 KB	Output is correct
18	Correct	15 ms	1020 KB	Output is correct
19	Correct	16 ms	1020 KB	Output is correct
20	Correct	24 ms	1020 KB	Output is correct
21	Correct	32 ms	1152 KB	Output is correct
22	Correct	28 ms	1152 KB	Output is correct
23	Correct	23 ms	1152 KB	Output is correct
24	Correct	28 ms	1404 KB	Output is correct
25	Correct	27 ms	1404 KB	Output is correct
26	Correct	27 ms	1404 KB	Output is correct
27	Correct	26 ms	1404 KB	Output is correct
28	Correct	31 ms	1404 KB	Output is correct
29	Correct	38 ms	1404 KB	Output is correct
30	Incorrect	39 ms	1660 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

답안 #61235

Compilation message

Subtask #1 7.0 / 7.0

Subtask #2 19.0 / 19.0

Subtask #3 0 / 29.0

Subtask #4 0 / 45.0

Subtask #1
7.0 / 7.0

Subtask #2
19.0 / 19.0

Subtask #3
0 / 29.0

Subtask #4
0 / 45.0