Submission #995052

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
995052	2024-06-08T11:39:03 Z	Requiem	Designated Cities (JOI19_designated_cities)	C++17	22 / 100	491 ms	55124 KB

designated_cities

#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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-