oj.uz

Submission #995063

# Submission time Handle Problem Language Result Execution time Memory
995063 2024-06-08T11:49:45 Z Requiem Designated Cities (JOI19_designated_cities) C++17
39 / 100
 892 ms 55120 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;
                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;
        }
    }
}
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:247:17: warning: unused variable 'leave1' [-Wunused-variable]
  247 |             int leave1 = maxdepth[i].se;
      |                 ^~~~~~
designated_cities.cpp: At global scope:
designated_cities.cpp:280:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  280 | main()
      | ^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:285:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  285 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:286:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  286 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 54 ms 22876 KB Output is correct
3 Correct 62 ms 22876 KB Output is correct
4 Correct 42 ms 22872 KB Output is correct
5 Correct 45 ms 22872 KB Output is correct
6 Correct 51 ms 22876 KB Output is correct
7 Correct 55 ms 22876 KB Output is correct
8 Correct 44 ms 22872 KB Output is correct
9 Correct 41 ms 22876 KB Output is correct
10 Correct 64 ms 22872 KB Output is correct
11 Correct 38 ms 22872 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23288 KB Output is correct
2 Correct 119 ms 31828 KB Output is correct
3 Correct 133 ms 43348 KB Output is correct
4 Correct 105 ms 32080 KB Output is correct
5 Correct 119 ms 31688 KB Output is correct
6 Correct 104 ms 33532 KB Output is correct
7 Correct 97 ms 31936 KB Output is correct
8 Correct 183 ms 44112 KB Output is correct
9 Correct 73 ms 32196 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22872 KB Output is correct
2 Correct 133 ms 33488 KB Output is correct
3 Correct 159 ms 55120 KB Output is correct
4 Correct 113 ms 33364 KB Output is correct
5 Correct 98 ms 35272 KB Output is correct
6 Correct 125 ms 38076 KB Output is correct
7 Correct 76 ms 33732 KB Output is correct
8 Correct 135 ms 44368 KB Output is correct
9 Correct 98 ms 32960 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 54 ms 22876 KB Output is correct
3 Correct 62 ms 22876 KB Output is correct
4 Correct 42 ms 22872 KB Output is correct
5 Correct 45 ms 22872 KB Output is correct
6 Correct 51 ms 22876 KB Output is correct
7 Correct 55 ms 22876 KB Output is correct
8 Correct 44 ms 22872 KB Output is correct
9 Correct 41 ms 22876 KB Output is correct
10 Correct 64 ms 22872 KB Output is correct
11 Correct 38 ms 22872 KB Output is correct
12 Correct 3 ms 22876 KB Output is correct
13 Correct 849 ms 23276 KB Output is correct
14 Correct 729 ms 23508 KB Output is correct
15 Correct 892 ms 23344 KB Output is correct
16 Correct 843 ms 23128 KB Output is correct
17 Correct 804 ms 23132 KB Output is correct
18 Correct 811 ms 23352 KB Output is correct
19 Correct 827 ms 23128 KB Output is correct
20 Correct 788 ms 23340 KB Output is correct
21 Correct 816 ms 23376 KB Output is correct
22 Correct 842 ms 23340 KB Output is correct
23 Correct 782 ms 23348 KB Output is correct
24 Correct 544 ms 23132 KB Output is correct
25 Correct 722 ms 23640 KB Output is correct
26 Correct 484 ms 23348 KB Output is correct

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23288 KB Output is correct
2 Correct 119 ms 31828 KB Output is correct
3 Correct 133 ms 43348 KB Output is correct
4 Correct 105 ms 32080 KB Output is correct
5 Correct 119 ms 31688 KB Output is correct
6 Correct 104 ms 33532 KB Output is correct
7 Correct 97 ms 31936 KB Output is correct
8 Correct 183 ms 44112 KB Output is correct
9 Correct 73 ms 32196 KB Output is correct
10 Correct 3 ms 22872 KB Output is correct
11 Correct 133 ms 33488 KB Output is correct
12 Correct 159 ms 55120 KB Output is correct
13 Correct 113 ms 33364 KB Output is correct
14 Correct 98 ms 35272 KB Output is correct
15 Correct 125 ms 38076 KB Output is correct
16 Correct 76 ms 33732 KB Output is correct
17 Correct 135 ms 44368 KB Output is correct
18 Correct 98 ms 32960 KB Output is correct
19 Correct 4 ms 22876 KB Output is correct
20 Incorrect 77 ms 30264 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB Output is correct
2 Correct 54 ms 22876 KB Output is correct
3 Correct 62 ms 22876 KB Output is correct
4 Correct 42 ms 22872 KB Output is correct
5 Correct 45 ms 22872 KB Output is correct
6 Correct 51 ms 22876 KB Output is correct
7 Correct 55 ms 22876 KB Output is correct
8 Correct 44 ms 22872 KB Output is correct
9 Correct 41 ms 22876 KB Output is correct
10 Correct 64 ms 22872 KB Output is correct
11 Correct 38 ms 22872 KB Output is correct
12 Correct 3 ms 23288 KB Output is correct
13 Correct 119 ms 31828 KB Output is correct
14 Correct 133 ms 43348 KB Output is correct
15 Correct 105 ms 32080 KB Output is correct
16 Correct 119 ms 31688 KB Output is correct
17 Correct 104 ms 33532 KB Output is correct
18 Correct 97 ms 31936 KB Output is correct
19 Correct 183 ms 44112 KB Output is correct
20 Correct 73 ms 32196 KB Output is correct
21 Correct 3 ms 22872 KB Output is correct
22 Correct 133 ms 33488 KB Output is correct
23 Correct 159 ms 55120 KB Output is correct
24 Correct 113 ms 33364 KB Output is correct
25 Correct 98 ms 35272 KB Output is correct
26 Correct 125 ms 38076 KB Output is correct
27 Correct 76 ms 33732 KB Output is correct
28 Correct 135 ms 44368 KB Output is correct
29 Correct 98 ms 32960 KB Output is correct
30 Correct 3 ms 22876 KB Output is correct
31 Correct 849 ms 23276 KB Output is correct
32 Correct 729 ms 23508 KB Output is correct
33 Correct 892 ms 23344 KB Output is correct
34 Correct 843 ms 23128 KB Output is correct
35 Correct 804 ms 23132 KB Output is correct
36 Correct 811 ms 23352 KB Output is correct
37 Correct 827 ms 23128 KB Output is correct
38 Correct 788 ms 23340 KB Output is correct
39 Correct 816 ms 23376 KB Output is correct
40 Correct 842 ms 23340 KB Output is correct
41 Correct 782 ms 23348 KB Output is correct
42 Correct 544 ms 23132 KB Output is correct
43 Correct 722 ms 23640 KB Output is correct
44 Correct 484 ms 23348 KB Output is correct
45 Correct 4 ms 22876 KB Output is correct
46 Incorrect 77 ms 30264 KB Output isn't correct
47 Halted 0 ms 0 KB -