oj.uz

Submission #44122

# Submission time Handle Problem Language Result Execution time Memory
44122 2018-03-30T05:41:41 Z Talant Fireworks (APIO16_fireworks) C++17
0 / 100
 6 ms 5408 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
#define int long long

using namespace std;

typedef long long ll;

const int inf = (int)1e9 + 7;
const int N = (int)2e5 + 7;

int n,m;
int cnt = 1;
int x,w,mn = inf;
int mx,dist[N];
int d[N],ans;

vector <pair<int,int> > g[N];
vector <int> e,vec;

void dfs (int v,int p = -1,int d = 0) {
      dist[v] = d;

      if (g[v].size() == 1 && v != 1)
            e.pb(d),vec.pb(v);

      for (auto to : g[v]) {
            if (to.fr != p)
                  dfs(to.fr,v,d + to.sc);
      }
}
void solve (int v,int cur,int p = -1) {
      for (auto to : g[v]) {
            if (p != to.fr) {
                  solve(to.fr,cur,v);
                  d[v] = min(d[to.fr],d[v]);
            }
      }
}
void calc (int v,int p = -1) {
      for (auto to : g[v]) {
            if (p != to.fr) {
                  ans += (d[to.fr] - d[v]);
                  calc(to.fr,v);
            }
      }
}
main () {
      cin >> n >> m;

      for (int i = 1; i < n + m; i ++) {
            cin >> x >> w;
            ++cnt;
            g[x].pb(mk(cnt,w));
            g[cnt].pb(mk(x,w));
      }

      dfs(1);


      for (int i = 0; i < e.size(); i ++) {
            for (int j = 0; j < vec.size(); j ++)
                  d[vec[j]] = abs(dist[vec[j]] - e[i]);
            solve (1,e[i]);
            calc(1);
            mn = min(mn,ans);
            for (int j = 1; j <= cnt; j ++) {
                  d[j] = inf;
            }
            ans = 0;
      }
      cout << mn << endl;
}

Compilation message

fireworks.cpp:53:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
fireworks.cpp: In function 'int main()':
fireworks.cpp:66:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int i = 0; i < e.size(); i ++) {
                       ~~^~~~~~~~~~
fireworks.cpp:67:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j = 0; j < vec.size(); j ++)
                             ~~^~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 5 ms 5228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 5408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 5 ms 5228 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Incorrect 5 ms 5228 KB Output isn't correct
3 Halted 0 ms 0 KB -