Submission #163906

#	Time	Username	Problem	Language	Result	Execution time	Memory
163906		combi1k1	Designated Cities (JOI19_designated_cities)	C++14	9 / 100	577 ms	49208 KiB

designated_cities

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define pb  emplace_back

#define int long long
#define ii  pair<int,int>
#define ed  tuple<int,int,int>

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

const int   N   = 2e5 + 5;

vector<ed>  g[N];
vector<int> vec;

int ans[N];
int re1 = 0;
int re2 = 0;

ii  dfs(int u,int p)    {
    ii  res(0,u);

    for(ed  e : g[u])   if (get<0>(e) != p) {
        int x, y, z;
        tie(x, y, z) = e;
        ii  cur = dfs(x,u); cur.X += y;
        res = max(res,cur);
    }
    return  res;
}

int cal(int u,int p)    {
    int M = 0;
    for(ed  e : g[u])   if (get<0>(e) != p) {
        int x, y, z;
        tie(x, y, z) = e;
        re1 += z;
        int t = cal(x,u) + y;
        if (t <= M) vec.pb(t);
        if (t >  M) vec.pb(M), M = t;
    }
    return  M;
}

void ini(int u,int p)   {
    for(ed  e : g[u])   if (get<0>(e) != p) {
        int x, y, z;
        tie(x, y, z) = e;
        re2 += z,
        ini(x,u);
    }
}
void sol(int u,int p)   {
    ans[1] = max(ans[1],re2);

    for(ed  e : g[u])   if (get<0>(e) != p) {
        int x, y, z;
        tie(x, y, z) = e;
        re2 += y - z;  cal(x,u);
        re2 -= y - z;
    }
}

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;
    int S = 0;

    FOR(i,1,n)  {
        int x, y;   cin >> x >> y;
        int c, d;   cin >> c >> d;
        g[x].pb(y,c,d);
        g[y].pb(x,d,c);
        S += c + d;
    }
    int L = dfs(1,0).Y;
    int R = dfs(L,0).Y;

    vec.pb(cal(R,0));

    sort(vec.begin(),vec.end(),greater<int>());

    ans[1] = re1;

    FOR(i,2,n + 1)
        ans[i] = ans[i - 1] + (i - 2 < vec.size() ? vec[i - 2] : 0);

    ini(1,0);
    sol(1,0);

    int q;  cin >> q;

    FOR(i,0,q)  {
        int x;  cin >> x;
        cout << S - ans[x] << "\n";
    }
}

Compilation message (stderr)

designated_cities.cpp: In function 'int main()':
designated_cities.cpp:92:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         ans[i] = ans[i - 1] + (i - 2 < vec.size() ? vec[i - 2] : 0);
                                ~~~~~~^~~~~~~~~~~~

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