Submission #44122

#	Time	Username	Problem	Language	Result	Execution time	Memory
44122		Talant	Fireworks (APIO16_fireworks)	C++17	0 / 100	6 ms	5408 KiB

fireworks

#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 (stderr)

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
• Subtask 2: 0 / 19
• Subtask 3: 0 / 29
• Subtask 4: 0 / 45