Submission #132343

#	Time	Username	Problem	Language	Result	Execution time	Memory
132343		duality	Construction of Highway (JOI18_construction)	C++11	16 / 100	2064 ms	16188 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

int C[100000];
vi adjList[100000];
int parent[100000],order[100000];
int depth[100000];
int disc[100000],fin[100000],inv[100000],num = 0;
int doDFS(int u,int d) {
    int i;
    depth[u] = d,disc[u] = num++,inv[num-1] = u;
    for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i],d+1);
    fin[u] = num;
    return 0;
}
int good[100000],pref[100000];
int main() {
    int i;
    int N,A,B;
    scanf("%d",&N);
    for (i = 0; i < N; i++) scanf("%d",&C[i]);
    parent[0] = -1;
    for (i = 0; i < N-1; i++) {
        scanf("%d %d",&A,&B);
        A--,B--;
        adjList[A].pb(B),parent[B] = A;
        order[i] = B;
    }
    doDFS(0,0);

    int j,k;
    for (i = 0; i < N; i++) pref[i] = -1;
    for (i = 0; i < N-1; i++) {
        int u = order[i];
        vpii vv;
        while (u != 0) {
            int v = pref[parent[u]];
            if (v != -1) good[v] = 0;
            pref[parent[u]] = u,good[u] = 1;
            int w = parent[u];
            while (good[w]) w = parent[w];
            if (v != -1) C[v] = C[w];
            vv.pb(mp(C[w],depth[u]-depth[w]));
            u = w;
        }
        LLI ans = 0;
        reverse(vv.begin(),vv.end());
        for (j = 0; j < vv.size(); j++) {
            for (k = j+1; k < vv.size(); k++) {
                if (vv[j].first > vv[k].first) ans += (LLI) vv[j].second*vv[k].second;
            }
        }
        printf("%lld\n",ans);
        C[0] = C[order[i]];
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int doDFS(int, int)':
construction.cpp:18:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) doDFS(adjList[u][i],d+1);
                 ~~^~~~~~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (j = 0; j < vv.size(); j++) {
                     ~~^~~~~~~~~~~
construction.cpp:55:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (k = j+1; k < vv.size(); k++) {
                           ~~^~~~~~~~~~~
construction.cpp:26:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
construction.cpp:27:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&C[i]);
                             ~~~~~^~~~~~~~~~~~
construction.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&A,&B);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84