Submission #995063

#	Time	Username	Problem	Language	Result	Execution time	Memory
995063		Requiem	Designated Cities (JOI19_designated_cities)	C++17	39 / 100	892 ms	55120 KiB

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 (stderr)

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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44