답안 #995063

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995063	2024-06-08T11:49:45 Z	Requiem	Designated Cities (JOI19_designated_cities)	C++17	39 / 100	892 ms	55120 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;
                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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-