oj.uz

Submission #1033718

# Submission time Handle Problem Language Result Execution time Memory
1033718 2024-07-25T04:20:23 Z Requiem Designated Cities (JOI19_designated_cities) C++17
100 / 100
 368 ms 79988 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{  //giai cho 2 dinh.
    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{  //giai cho n = 2
    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;
                maxdepth[j] = ii(0, 0);
            }
            st.clear();
            dfs(i, -1);

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

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

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

//            cout << dp[i] << ' ' << maxdepth[i].fi << ' ' << maxdepth[i].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);
            }
//            cout << endl;
        }

        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;
        }
    }
}

namespace subtask6{
    bool check(){
         return true;
    }

    //Ta co nhan xet la dap an cua 2 dinh se nam trong dap an cua k dinh (k >= 2)
    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];

        }
    }

    int dpForTwo[MAXN], maxDepthForTwo[MAXN], ansForTwo = 0, bestU = 0;

    void dfs1(int u, int p){
         maxDepthForTwo[u] = 0;

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

    void transition(int u, int v, int id){   //di tu u den v
         dpForTwo[u] -= dpForTwo[v] + edge[rev(id)].fi;
         dpForTwo[v] += dpForTwo[u] + edge[id].fi;
    }

    void update(ii &res, int v){
         if (res.fi < v){
             res.se = res.fi;
             res.fi = v;
         }
         else if (res.se < v){
             res.se = v;
         }
    }
    void dfs2(int u, int p, int maxDepth){
         ii bestDepth = ii(maxDepth, -inf);
         maximize(answer[1], dpForTwo[u]);

         for(auto id: g[u]){
             int v = edge[id].se;
             if (v != p) update(bestDepth, maxDepthForTwo[v] + edge[id].fi);
         }
         if (maximize(ansForTwo, dpForTwo[u] + bestDepth.fi)){
             bestU = u;
         }
//         cout << u << ' ' << dpForTwo[u] << ' ' << bestDepth.fi << ' ' << bestDepth.se << endl;

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

             dfs2(v, u, edge[rev(id)].fi + ((maxDepthForTwo[v] + edge[id].fi == bestDepth.fi) ? bestDepth.se : bestDepth.fi)) ;

             transition(v, u, rev(id));
         }
    }
    void solveForTwo(){
         dfs1(1, -1);
         dfs2(1, -1, 0);
    }
    void solve(){
            solveForTwo();
            for(int j = 1; j <= n; j++){
                dp[j] = del[j] = 0;
                maxdepth[j] = ii(0, 0);
            }
            st.clear();
            dfs(bestU, -1);

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

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

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

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

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

        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;

    if (subtask6::check()) return subtask6::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:247:17: warning: unused variable 'leave1' [-Wunused-variable]
  247 |             int leave1 = maxdepth[i].se;
      |                 ^~~~~~
designated_cities.cpp: In function 'void subtask6::solve()':
designated_cities.cpp:387:17: warning: unused variable 'leave1' [-Wunused-variable]
  387 |             int leave1 = maxdepth[bestU].se;
      |                 ^~~~~~
designated_cities.cpp: At global scope:
designated_cities.cpp:419:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  419 | main()
      | ^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:424:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  424 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:425:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  425 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14172 KB Output is correct
2 Correct 6 ms 14220 KB Output is correct
3 Correct 5 ms 14172 KB Output is correct
4 Correct 5 ms 14172 KB Output is correct
5 Correct 5 ms 14024 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 4 ms 14172 KB Output is correct
9 Correct 5 ms 14168 KB Output is correct
10 Correct 4 ms 14172 KB Output is correct
11 Correct 4 ms 14024 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14172 KB Output is correct
2 Correct 281 ms 59112 KB Output is correct
3 Correct 260 ms 76884 KB Output is correct
4 Correct 252 ms 57684 KB Output is correct
5 Correct 254 ms 59016 KB Output is correct
6 Correct 238 ms 61520 KB Output is correct
7 Correct 204 ms 59336 KB Output is correct
8 Correct 277 ms 76112 KB Output is correct
9 Correct 155 ms 59748 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14168 KB Output is correct
2 Correct 262 ms 59140 KB Output is correct
3 Correct 270 ms 76992 KB Output is correct
4 Correct 239 ms 57880 KB Output is correct
5 Correct 256 ms 59088 KB Output is correct
6 Correct 245 ms 61996 KB Output is correct
7 Correct 211 ms 59328 KB Output is correct
8 Correct 248 ms 70480 KB Output is correct
9 Correct 156 ms 59496 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14172 KB Output is correct
2 Correct 6 ms 14220 KB Output is correct
3 Correct 5 ms 14172 KB Output is correct
4 Correct 5 ms 14172 KB Output is correct
5 Correct 5 ms 14024 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 4 ms 14172 KB Output is correct
9 Correct 5 ms 14168 KB Output is correct
10 Correct 4 ms 14172 KB Output is correct
11 Correct 4 ms 14024 KB Output is correct
12 Correct 4 ms 14168 KB Output is correct
13 Correct 6 ms 14684 KB Output is correct
14 Correct 7 ms 14684 KB Output is correct
15 Correct 6 ms 14684 KB Output is correct
16 Correct 6 ms 14556 KB Output is correct
17 Correct 8 ms 14684 KB Output is correct
18 Correct 6 ms 14680 KB Output is correct
19 Correct 6 ms 14684 KB Output is correct
20 Correct 6 ms 14684 KB Output is correct
21 Correct 6 ms 14684 KB Output is correct
22 Correct 6 ms 14684 KB Output is correct
23 Correct 6 ms 14656 KB Output is correct
24 Correct 6 ms 14684 KB Output is correct
25 Correct 6 ms 14684 KB Output is correct
26 Correct 6 ms 14592 KB Output is correct

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14172 KB Output is correct
2 Correct 281 ms 59112 KB Output is correct
3 Correct 260 ms 76884 KB Output is correct
4 Correct 252 ms 57684 KB Output is correct
5 Correct 254 ms 59016 KB Output is correct
6 Correct 238 ms 61520 KB Output is correct
7 Correct 204 ms 59336 KB Output is correct
8 Correct 277 ms 76112 KB Output is correct
9 Correct 155 ms 59748 KB Output is correct
10 Correct 5 ms 14168 KB Output is correct
11 Correct 262 ms 59140 KB Output is correct
12 Correct 270 ms 76992 KB Output is correct
13 Correct 239 ms 57880 KB Output is correct
14 Correct 256 ms 59088 KB Output is correct
15 Correct 245 ms 61996 KB Output is correct
16 Correct 211 ms 59328 KB Output is correct
17 Correct 248 ms 70480 KB Output is correct
18 Correct 156 ms 59496 KB Output is correct
19 Correct 5 ms 14172 KB Output is correct
20 Correct 315 ms 59036 KB Output is correct
21 Correct 278 ms 76968 KB Output is correct
22 Correct 257 ms 57684 KB Output is correct
23 Correct 276 ms 59304 KB Output is correct
24 Correct 280 ms 57936 KB Output is correct
25 Correct 297 ms 59408 KB Output is correct
26 Correct 263 ms 57980 KB Output is correct
27 Correct 277 ms 59084 KB Output is correct
28 Correct 275 ms 61568 KB Output is correct
29 Correct 280 ms 59220 KB Output is correct
30 Correct 262 ms 58260 KB Output is correct
31 Correct 231 ms 59332 KB Output is correct
32 Correct 284 ms 71272 KB Output is correct
33 Correct 180 ms 59772 KB Output is correct

Subtask #6
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14172 KB Output is correct
2 Correct 6 ms 14220 KB Output is correct
3 Correct 5 ms 14172 KB Output is correct
4 Correct 5 ms 14172 KB Output is correct
5 Correct 5 ms 14024 KB Output is correct
6 Correct 4 ms 14172 KB Output is correct
7 Correct 4 ms 14172 KB Output is correct
8 Correct 4 ms 14172 KB Output is correct
9 Correct 5 ms 14168 KB Output is correct
10 Correct 4 ms 14172 KB Output is correct
11 Correct 4 ms 14024 KB Output is correct
12 Correct 4 ms 14172 KB Output is correct
13 Correct 281 ms 59112 KB Output is correct
14 Correct 260 ms 76884 KB Output is correct
15 Correct 252 ms 57684 KB Output is correct
16 Correct 254 ms 59016 KB Output is correct
17 Correct 238 ms 61520 KB Output is correct
18 Correct 204 ms 59336 KB Output is correct
19 Correct 277 ms 76112 KB Output is correct
20 Correct 155 ms 59748 KB Output is correct
21 Correct 5 ms 14168 KB Output is correct
22 Correct 262 ms 59140 KB Output is correct
23 Correct 270 ms 76992 KB Output is correct
24 Correct 239 ms 57880 KB Output is correct
25 Correct 256 ms 59088 KB Output is correct
26 Correct 245 ms 61996 KB Output is correct
27 Correct 211 ms 59328 KB Output is correct
28 Correct 248 ms 70480 KB Output is correct
29 Correct 156 ms 59496 KB Output is correct
30 Correct 4 ms 14168 KB Output is correct
31 Correct 6 ms 14684 KB Output is correct
32 Correct 7 ms 14684 KB Output is correct
33 Correct 6 ms 14684 KB Output is correct
34 Correct 6 ms 14556 KB Output is correct
35 Correct 8 ms 14684 KB Output is correct
36 Correct 6 ms 14680 KB Output is correct
37 Correct 6 ms 14684 KB Output is correct
38 Correct 6 ms 14684 KB Output is correct
39 Correct 6 ms 14684 KB Output is correct
40 Correct 6 ms 14684 KB Output is correct
41 Correct 6 ms 14656 KB Output is correct
42 Correct 6 ms 14684 KB Output is correct
43 Correct 6 ms 14684 KB Output is correct
44 Correct 6 ms 14592 KB Output is correct
45 Correct 5 ms 14172 KB Output is correct
46 Correct 315 ms 59036 KB Output is correct
47 Correct 278 ms 76968 KB Output is correct
48 Correct 257 ms 57684 KB Output is correct
49 Correct 276 ms 59304 KB Output is correct
50 Correct 280 ms 57936 KB Output is correct
51 Correct 297 ms 59408 KB Output is correct
52 Correct 263 ms 57980 KB Output is correct
53 Correct 277 ms 59084 KB Output is correct
54 Correct 275 ms 61568 KB Output is correct
55 Correct 280 ms 59220 KB Output is correct
56 Correct 262 ms 58260 KB Output is correct
57 Correct 231 ms 59332 KB Output is correct
58 Correct 284 ms 71272 KB Output is correct
59 Correct 180 ms 59772 KB Output is correct
60 Correct 4 ms 14168 KB Output is correct
61 Correct 305 ms 63388 KB Output is correct
62 Correct 367 ms 79988 KB Output is correct
63 Correct 269 ms 62036 KB Output is correct
64 Correct 325 ms 63316 KB Output is correct
65 Correct 310 ms 62000 KB Output is correct
66 Correct 296 ms 63284 KB Output is correct
67 Correct 264 ms 62076 KB Output is correct
68 Correct 288 ms 63492 KB Output is correct
69 Correct 303 ms 65916 KB Output is correct
70 Correct 368 ms 63312 KB Output is correct
71 Correct 317 ms 62664 KB Output is correct
72 Correct 259 ms 64192 KB Output is correct
73 Correct 347 ms 74836 KB Output is correct
74 Correct 221 ms 65568 KB Output is correct