oj.uz

답안 #1030548

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1030548 2024-07-22T06:42:32 Z 김은성(#10955) Designated Cities (JOI19_designated_cities) C++17
23 / 100
 2000 ms 32992 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans[200009];
bool ch[200009];
const ll INF = 0x3fffffffffffffff;
vector<pair<int, ll> > graph[200009];
vector<pair<int, ll> > tree[200009];
ll depth[200009], sum = 0;
int par[200009];
void construct_tree(int v){
    ch[v] = 1;
    for(int i=0; i<graph[v].size(); i++){
        int u = graph[v][i].first;
        if(!ch[u]){
            sum += graph[v][i].second;
            tree[v].push_back(graph[v][i]);
            par[u] = v;
            construct_tree(u);
        }
    }
}
int deepest_vertex(int v, ll d){
    depth[v] = d;
    ch[v] = 1;
    int ans = v;
    for(int i=0; i<tree[v].size(); i++){
        int u = tree[v][i].first;
        if(!ch[u]){
            int x = deepest_vertex(u, d+tree[v][i].second);
            if(depth[x] > depth[ans])
                ans = x;
        }
    }
    return ans;
}
void delete_edge(int v, int r){
    int p = par[v];
    while(v != r){
        for(int i=0; i<tree[p].size(); i++){
            if(tree[p][i].first == v)
                tree[p][i].second = 0;
        }
        v = p;
        p = par[v];
    }
}
int main(){
    int n, i, j, a, b, q, v;
    ll c, d;
    scanf("%d", &n);
    for(i=1; i<n; i++){
        scanf("%d %d %lld %lld", &a, &b, &c, &d);
        graph[a].push_back(make_pair(b, c));
        graph[b].push_back(make_pair(a, d));
    }
    for(i=1; i<=n; i++)
        ans[i] = INF;
    for(i=1; i<=n; i++){
        for(j=1; j<=n; j++){
            tree[j].clear();
            ch[j] = 0;
        }
        sum = 0;
        construct_tree(i);
        ans[1] = min(ans[1], sum);
        for(j=1; j<=n; j++){
            ans[j] = min(ans[j], sum);
            for(int k=1; k<=n; k++)
                ch[k]=0;
            int v = deepest_vertex(i, 0);
            if(v>=i)
                break;
            sum -= depth[v];
            delete_edge(v, i);
        }
    }
    scanf("%d", &q);
    for(i=2; i<=n; i++){
        ans[i] = min(ans[i-1], ans[i]);
    }
    while(q--){
        scanf("%d", &v);
        printf("%lld\n", ans[v]);
    }
    return 0;
}

Compilation message

designated_cities.cpp: In function 'void construct_tree(int)':
designated_cities.cpp:13:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0; i<graph[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~~~
designated_cities.cpp: In function 'int deepest_vertex(int, ll)':
designated_cities.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0; i<tree[v].size(); i++){
      |                  ~^~~~~~~~~~~~~~~
designated_cities.cpp: In function 'void delete_edge(int, int)':
designated_cities.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int i=0; i<tree[p].size(); i++){
      |                      ~^~~~~~~~~~~~~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
designated_cities.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d %lld %lld", &a, &b, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
designated_cities.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |         scanf("%d", &v);
      |         ~~~~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9620 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9780 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9848 KB Output is correct
11 Correct 4 ms 9620 KB Output is correct

Subtask #2
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Execution timed out 2068 ms 32992 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Execution timed out 2049 ms 32900 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9620 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9780 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9848 KB Output is correct
11 Correct 4 ms 9620 KB Output is correct
12 Correct 5 ms 9816 KB Output is correct
13 Correct 172 ms 10072 KB Output is correct
14 Correct 172 ms 10276 KB Output is correct
15 Correct 155 ms 10072 KB Output is correct
16 Correct 136 ms 10116 KB Output is correct
17 Correct 218 ms 10072 KB Output is correct
18 Correct 206 ms 10072 KB Output is correct
19 Correct 213 ms 10072 KB Output is correct
20 Correct 201 ms 10124 KB Output is correct
21 Correct 192 ms 10076 KB Output is correct
22 Correct 413 ms 10120 KB Output is correct
23 Correct 304 ms 10076 KB Output is correct
24 Correct 233 ms 10076 KB Output is correct
25 Correct 440 ms 10076 KB Output is correct
26 Correct 169 ms 10128 KB Output is correct

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Execution timed out 2068 ms 32992 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Correct 4 ms 9620 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9780 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9820 KB Output is correct
8 Correct 4 ms 9820 KB Output is correct
9 Correct 4 ms 9820 KB Output is correct
10 Correct 4 ms 9848 KB Output is correct
11 Correct 4 ms 9620 KB Output is correct
12 Correct 5 ms 9820 KB Output is correct
13 Execution timed out 2068 ms 32992 KB Time limit exceeded
14 Halted 0 ms 0 KB -