Submission #163906

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
163906	2019-11-16T07:02:11 Z	combi1k1	Designated Cities (JOI19_designated_cities)	C++14	9 / 100	577 ms	49208 KB

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

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.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	18 ms	5116 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	6 ms	5112 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	407 ms	30424 KB	Output is correct
3	Correct	577 ms	49208 KB	Output is correct
4	Correct	385 ms	29032 KB	Output is correct
5	Correct	396 ms	31208 KB	Output is correct
6	Correct	438 ms	33616 KB	Output is correct
7	Correct	252 ms	31268 KB	Output is correct
8	Correct	556 ms	42596 KB	Output is correct
9	Correct	236 ms	30868 KB	Output is correct