제출 #995001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
995001		Requiem	Designated Cities (JOI19_designated_cities)	C++17	16 / 100	161 ms	61272 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 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;
    }
}
main()
{
    fast;
    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 (subtask2::check()) return subtask2::solve(), 0;
    if (subtask3::check()) return subtask3::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
**/

컴파일 시 표준 에러 (stderr) 메시지

designated_cities.cpp:155:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  155 | main()
      | ^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:159:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  159 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
designated_cities.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 17
• Subtask 5: 0 / 17
• Subtask 6: 0 / 44