oj.uz

Submission #202040

# Submission time Handle Problem Language Result Execution time Memory
202040 2020-02-13T08:20:53 Z theStaticMind Designated Cities (JOI19_designated_cities) C++14
7 / 100
 1320 ms 69624 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

vector<int> adj[200005];
vector<int> val(200005);
vector<int> ans(200005, 0);
map<ii, int> cost;
int S = 0;

void dfs1(int x, int pre, int& v){
      for(int i = 0; i < adj[x].size(); i++){
            int y = adj[x][i];
            if(y == pre) continue;
            v += cost[{y, x}];
            dfs1(y, x, v);
      }
}
void dfs2(int x, int pre, int v){
      val[x] = v;
      for(int i = 0; i < adj[x].size(); i++){
            int y = adj[x][i];
            if(y == pre) continue;
            dfs2(y, x, v - cost[{y, x}] + cost[{x, y}]);
      }
}

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
//      freopen("q.gir","r",stdin);
//      freopen("q.cik","w",stdout);
      int n;
      cin >> n;
      for(int i = 0; i < n - 1; i++){
            int x, y, a, b;
            cin >> x >> y >> a >> b;
            adj[x].pb(y);
            adj[y].pb(x);
            cost[{x, y}] = a;
            cost[{y, x}] = b;
            S += a + b;
      }
      int w = 0;
      dfs1(1, 0, w);
      dfs2(1, 0, w);
      ans[1] = S - *max_element(all(val));

      int q;
      cin >> q;
      while(q--){
            int k;
            cin >> k;
            cout << ans[k] << "\n";
      }
}

Compilation message

designated_cities.cpp: In function 'void dfs1(long long int, long long int, long long int&)':
designated_cities.cpp:18:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < adj[x].size(); i++){
                      ~~^~~~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs2(long long int, long long int, long long int)':
designated_cities.cpp:27:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < adj[x].size(); i++){
                      ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Incorrect 10 ms 8184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Correct 1181 ms 47292 KB Output is correct
3 Correct 1238 ms 68984 KB Output is correct
4 Correct 1218 ms 45816 KB Output is correct
5 Correct 1320 ms 47088 KB Output is correct
6 Correct 1309 ms 50188 KB Output is correct
7 Correct 1158 ms 47088 KB Output is correct
8 Correct 1280 ms 69624 KB Output is correct
9 Correct 939 ms 47840 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Incorrect 1222 ms 46976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Incorrect 10 ms 8184 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Correct 1181 ms 47292 KB Output is correct
3 Correct 1238 ms 68984 KB Output is correct
4 Correct 1218 ms 45816 KB Output is correct
5 Correct 1320 ms 47088 KB Output is correct
6 Correct 1309 ms 50188 KB Output is correct
7 Correct 1158 ms 47088 KB Output is correct
8 Correct 1280 ms 69624 KB Output is correct
9 Correct 939 ms 47840 KB Output is correct
10 Correct 10 ms 8184 KB Output is correct
11 Incorrect 1222 ms 46976 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8184 KB Output is correct
2 Incorrect 10 ms 8184 KB Output isn't correct
3 Halted 0 ms 0 KB -