oj.uz

답안 #995052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
995052 2024-06-08T11:39:03 Z Requiem Designated Cities (JOI19_designated_cities) C++17
22 / 100
 491 ms 55124 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "designated"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair<ii, ii> iiii;
typedef vector<int> vi;
const int MAXN = 5e5 + 9;

ii edge[MAXN];
vector<int> g[MAXN];
int n, q, E[MAXN];

int rev(int x){
    return ((x&1) ? (x + 1) : (x - 1));
}

namespace subtask1{
    bool check(){
        return n <= 16;
    }

    int answer[MAXN], pave[MAXN * 2];
    void paved(int u, int p){
//         cerr << u << ' ' << p << endl;
         for(auto id: g[u]){
             int v = edge[id].se;
             int w = edge[id].fi;

             if (v == p) continue;
             paved(v, u);
             pave[rev(id)]++;
         }
    }
    void solve(){
         memset(answer, 0x3f, sizeof(answer));
         for(int i = 1; i < (1 << n); i++){
             for(int j = 0; j < 2 * n; j++){
                 pave[j] = 0;
             }
             for(int j = 0; j < n; j++){
                 if (i & (1 << j)) paved(j + 1, -1);
             }

             int cur = 0;
             for(int j = 1; j < 2 * n; j++){
                 if (pave[j] == 0) cur += edge[j].fi;
             }

             minimize(answer[__builtin_popcount(i)], cur);
         }

         for(int i = 1; i <= q; i++){
             cout << answer[E[i]] << endl;
         }
    }
}
namespace subtask2{
     bool check(){
          return (q == 1 and E[1] == 1);
     }

     int dp[MAXN];

     void dfs1(int u, int p){
          for(auto id: g[u]){
              int v = edge[id].se;
              if (v == p) continue;
              dfs1(v, u);
              int revid = rev(id);
              dp[u] += edge[revid].fi + dp[v];
          }
     }

     void transition(int u ,int v, int id){ //chuyen trang thai tu u sang v voi canh dang xet la id.
          dp[u] -= dp[v] + edge[rev(id)].fi;
          dp[v] += dp[u] + edge[id].fi;
     }

     int ans = 0;
     void dfs2(int u, int p){
          maximize(ans, dp[u]);

          for(auto id: g[u]){
              int v = edge[id].se;
              if (v == p) continue;

              transition(u, v, id);

              dfs2(v, u);

              transition(v, u, rev(id));
          }
     }
     void solve(){
          dfs1(1, -1);
          dfs2(1, -1);
          int sum = 0;
          for(int i = 1; i < 2 * n; i++){
              sum += edge[i].fi;
          }

          cout << sum - ans << endl;
     }
}

namespace subtask3{
    bool check(){
        return (q == 1 and E[1] == 2);
    }

    int dp[MAXN], maxdepth[MAXN], ans = 0;
    void dfs1(int u, int p){
         for(auto id: g[u]){
             int v = edge[id].se;
             if (v == p) continue;

             dfs1(v, u);

             dp[u] += edge[rev(id)].fi + dp[v];
             maximize(maxdepth[u], maxdepth[v] + edge[id].fi);
         }
    }

    void update(ii &a, int b){
        if (a.fi < b){
            a.se = a.fi;
            a.fi = b;
        }
        else if (a.se < b){
            a.se = b;
        }
    }

     void transition(int u ,int v, int id){ //chuyen trang thai tu u sang v voi canh dang xet la id.
          dp[u] -= dp[v] + edge[rev(id)].fi;
          dp[v] += dp[u] + edge[id].fi;
     }

    void dfs2(int u, int p, int mxd){
         ii pairs = {-inf, -inf};
         maximize(ans, dp[u] + max(mxd, maxdepth[u]));

         update(pairs, mxd);

//         cout << u << ' ' << mxd << ' ' << dp[u] << ' ' << ' ' << maxdepth[u] << ' ' << endl;
         for(auto id: g[u]){
             int v = edge[id].se;
             if (v == p) continue;
             update(pairs, maxdepth[v] + edge[id].fi);
         }

         for(auto id: g[u]){
             int v = edge[id].se;


             if (v == p) continue;

             transition(u, v, id);

             if (maxdepth[v] + edge[id].fi == pairs.fi){
                 dfs2(v, u, pairs.se + edge[rev(id)].fi);
             }
             else{
                 dfs2(v, u, pairs.fi + edge[rev(id)].fi);
             }

             transition(v, u, rev(id));
         }
    }
    void solve(){
        dfs1(1, -1);
        dfs2(1, -1, 0);

        int sum = 0;
        for(int i = 1; i < 2 * n; i++){
            sum += edge[i].fi;
        }
        cout << sum - ans << endl;
    }
}

namespace subtask4{
    bool check(){
        return n <= 2000;
    }

    int dp[MAXN], par[MAXN], del[MAXN], answer[MAXN];
    ii maxdepth[MAXN];
    multiset<ii> st;


    void dfs(int u, int p){
        maxdepth[u] = {0, u};
        for(auto id: g[u]){
            int v = edge[id].se;
            if (v == p) continue;

            dfs(v, u);
            par[v] = u;

            dp[u] += dp[v] + edge[rev(id)].fi;

            maxdepth[v].fi += edge[id].fi;
            maximize(maxdepth[u], maxdepth[v]);
        }
    }

    void deleteNode(int u){
        while(del[u] == 0){
            if (st.find(maxdepth[u]) != st.end()) st.erase(st.find(maxdepth[u]));
            del[u] = 1;
            u = par[u];

        }

    }
    void solve(){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                dp[j] = del[j] = 0;
            }
            st.clear();
            dfs(i, -1);

            for(int j = 2; j <= n; j++){
                st.insert(maxdepth[j]);
            }
            maximize(answer[1], dp[i]);

            del[1] = true;
            int leave1 = maxdepth[1].se;
            dp[i] += maxdepth[1].fi;

            maximize(answer[2], dp[i]);
            deleteNode(maxdepth[1].se);

//            cout << maxdepth[1].fi << ' ' << maxdepth[1].se << endl;

            for(int j = 3; j <= n; j++){
//                cout << st.size() << endl;
                if (st.size() == 0) {
                    maximize(answer[j], dp[i]);
                    continue;
                }
                ii it = *(--st.end());
//                cout << it.fi << ' ' << it.se <<endl;
                dp[i] += it.fi;
                maximize(answer[j], dp[i]);
                deleteNode(it.se);
            }
        }

        int sum = 0;
        for(int i = 1; i < 2 * n; i++){
            sum += edge[i].fi;
        }

        for(int i = 1; i <= q; i++){
            cout << sum - answer[E[i]] << endl;
        }
    }
}
main()
{
    fast;
    cerr.tie(NULL);
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }

    cin >> n;
    for(int i = 0; i < n - 1; i++){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        edge[2 * i + 1] = {c, v};
        edge[2 * i + 2] = {d, u};

        g[u].pb(2 * i + 1);
        g[v].pb(2 * i + 2);
    }

    cin >> q;
    for(int i = 1; i <= q; i++){
        cin >> E[i];
    }

    if (subtask1::check()) return subtask1::solve(), 0;

    if (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;

    if (subtask4::check()) return subtask4::solve(), 0;
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message

designated_cities.cpp: In function 'void subtask1::paved(long long int, long long int)':
designated_cities.cpp:42:18: warning: unused variable 'w' [-Wunused-variable]
   42 |              int w = edge[id].fi;
      |                  ^
designated_cities.cpp: In function 'void subtask4::solve()':
designated_cities.cpp:246:17: warning: unused variable 'leave1' [-Wunused-variable]
  246 |             int leave1 = maxdepth[1].se;
      |                 ^~~~~~
designated_cities.cpp: At global scope:
designated_cities.cpp:278:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  278 | main()
      | ^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:283:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  283 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:284:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  284 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 51 ms 22876 KB Output is correct
3 Correct 62 ms 22872 KB Output is correct
4 Correct 42 ms 22872 KB Output is correct
5 Correct 46 ms 22876 KB Output is correct
6 Correct 47 ms 22876 KB Output is correct
7 Correct 64 ms 22872 KB Output is correct
8 Correct 45 ms 22872 KB Output is correct
9 Correct 38 ms 22872 KB Output is correct
10 Correct 62 ms 22876 KB Output is correct
11 Correct 39 ms 22872 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 110 ms 31816 KB Output is correct
3 Correct 135 ms 43408 KB Output is correct
4 Correct 90 ms 31824 KB Output is correct
5 Correct 91 ms 31684 KB Output is correct
6 Correct 105 ms 33620 KB Output is correct
7 Correct 84 ms 31936 KB Output is correct
8 Correct 139 ms 43860 KB Output is correct
9 Correct 68 ms 32188 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 111 ms 33472 KB Output is correct
3 Correct 132 ms 55124 KB Output is correct
4 Correct 89 ms 33232 KB Output is correct
5 Correct 116 ms 35272 KB Output is correct
6 Correct 100 ms 38228 KB Output is correct
7 Correct 86 ms 33732 KB Output is correct
8 Correct 127 ms 44372 KB Output is correct
9 Correct 66 ms 32956 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 51 ms 22876 KB Output is correct
3 Correct 62 ms 22872 KB Output is correct
4 Correct 42 ms 22872 KB Output is correct
5 Correct 46 ms 22876 KB Output is correct
6 Correct 47 ms 22876 KB Output is correct
7 Correct 64 ms 22872 KB Output is correct
8 Correct 45 ms 22872 KB Output is correct
9 Correct 38 ms 22872 KB Output is correct
10 Correct 62 ms 22876 KB Output is correct
11 Correct 39 ms 22872 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Incorrect 491 ms 23340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 110 ms 31816 KB Output is correct
3 Correct 135 ms 43408 KB Output is correct
4 Correct 90 ms 31824 KB Output is correct
5 Correct 91 ms 31684 KB Output is correct
6 Correct 105 ms 33620 KB Output is correct
7 Correct 84 ms 31936 KB Output is correct
8 Correct 139 ms 43860 KB Output is correct
9 Correct 68 ms 32188 KB Output is correct
10 Correct 3 ms 22876 KB Output is correct
11 Correct 111 ms 33472 KB Output is correct
12 Correct 132 ms 55124 KB Output is correct
13 Correct 89 ms 33232 KB Output is correct
14 Correct 116 ms 35272 KB Output is correct
15 Correct 100 ms 38228 KB Output is correct
16 Correct 86 ms 33732 KB Output is correct
17 Correct 127 ms 44372 KB Output is correct
18 Correct 66 ms 32956 KB Output is correct
19 Correct 4 ms 22872 KB Output is correct
20 Incorrect 75 ms 30160 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 51 ms 22876 KB Output is correct
3 Correct 62 ms 22872 KB Output is correct
4 Correct 42 ms 22872 KB Output is correct
5 Correct 46 ms 22876 KB Output is correct
6 Correct 47 ms 22876 KB Output is correct
7 Correct 64 ms 22872 KB Output is correct
8 Correct 45 ms 22872 KB Output is correct
9 Correct 38 ms 22872 KB Output is correct
10 Correct 62 ms 22876 KB Output is correct
11 Correct 39 ms 22872 KB Output is correct
12 Correct 4 ms 22876 KB Output is correct
13 Correct 110 ms 31816 KB Output is correct
14 Correct 135 ms 43408 KB Output is correct
15 Correct 90 ms 31824 KB Output is correct
16 Correct 91 ms 31684 KB Output is correct
17 Correct 105 ms 33620 KB Output is correct
18 Correct 84 ms 31936 KB Output is correct
19 Correct 139 ms 43860 KB Output is correct
20 Correct 68 ms 32188 KB Output is correct
21 Correct 3 ms 22876 KB Output is correct
22 Correct 111 ms 33472 KB Output is correct
23 Correct 132 ms 55124 KB Output is correct
24 Correct 89 ms 33232 KB Output is correct
25 Correct 116 ms 35272 KB Output is correct
26 Correct 100 ms 38228 KB Output is correct
27 Correct 86 ms 33732 KB Output is correct
28 Correct 127 ms 44372 KB Output is correct
29 Correct 66 ms 32956 KB Output is correct
30 Correct 3 ms 22876 KB Output is correct
31 Incorrect 491 ms 23340 KB Output isn't correct
32 Halted 0 ms 0 KB -