Submission #425866

#	Time	Username	Problem	Language	Result	Execution time	Memory
425866		duality	Inside information (BOI21_servers)	C++11	100 / 100	2673 ms	84632 KiB

servers

#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 a[240000],b[240000];
vpii adjList[120000];
int parent[120000][17],good[120000][17],pe[120000],depth[120000],sum[120000];
int disc[120000],fin[120000],disc2[120000],num2 = 0,num3 = 0;
vi order,child[120000];
pii sparse[240000][18];
int logg[240001];
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,depth[u] = d,disc[u] = num2++,order.pb(u);
    disc2[u] = num3++,sparse[num3-1][0] = mp(d,u);
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i].first;
        if (v != p) child[u].pb(v),pe[v] = adjList[u][i].second,doDFS(v,u,d+1),sparse[num3++][0] = mp(d,u);
    }
    fin[u] = num2;
    return 0;
}
vpii edges;
int num[120000];
vi vv;
int lca(int u,int v) {
    u = disc2[u],v = disc2[v];
    if (u > v) swap(u,v);
    int l = logg[v-u+1];
    return min(sparse[u][l],sparse[v-(1 << l)+1][l]).second;
}
int getChild(int u,int v) {
    int l = 0,r = child[u].size()-1;
    while (l < r) {
        int m = (l+r+1) / 2;
        if (disc[child[u][m]] <= disc[v]) l = m;
        else r = m-1;
    }
    return child[u][l];
}
int path(int u,int v,int c) {
    if (u == v) return 1;
    int l = lca(u,v);
    if (l == u) {
        if (pe[v] > c) return 0;
        if (sum[v]-sum[getChild(l,v)] != -(depth[v]-depth[l]-1)) return 0;
        return 1;
    }
    else if (l == v) {
        int x = getChild(l,u);
        if (sum[u]-sum[x] != depth[u]-depth[l]-1) return 0;
        if (pe[x] > c) return 0;
        return 1;
    }
    else {
        if (pe[v] > c) return 0;
        int y = getChild(l,v);
        if (sum[v]-sum[y] != -(depth[v]-depth[l]-1)) return 0;
        int x = getChild(l,u);
        if (sum[u]-sum[x] != depth[u]-depth[l]-1) return 0;
        return pe[x] < pe[y];
    }
}
int main() {
    int i;
    int N,K;
    char c;
    scanf("%d %d",&N,&K);
    for (i = 0; i < N+K-1; i++) {
        scanf(" %c",&c);
        if (c == 'S') {
            scanf("%d %d",&a[i],&b[i]);
            a[i]--,b[i]--;
            adjList[a[i]].pb(mp(b[i],i));
            adjList[b[i]].pb(mp(a[i],i));
        }
        else if (c == 'Q') {
            scanf("%d %d",&a[i],&b[i]);
            a[i]--,b[i] *= -1;
        }
        else scanf("%d",&b[i]),a[i] = -1,b[i]--;
    }

    int j,k;
    doDFS(0,-1,0);
    for (i = 0; i < N; i++) {
        if ((parent[i][0] != -1) && (parent[parent[i][0]][0] != -1)) good[i][0] = (pe[i] < pe[parent[i][0]]) ? 1:-1;
        else good[i][0] = 0;
    }
    for (i = 1; i < N; i++) {
        int u = order[i];
        sum[u] = good[u][0]+sum[parent[u][0]];
    }
    for (i = 1; (1 << i) <= 2*N; i++) {
        for (j = 0; j <= 2*N-(1 << i); j++) sparse[j][i] = min(sparse[j][i-1],sparse[j+(1 << (i-1))][i-1]);
    }
    for (i = 2; i <= 2*N; i++) logg[i] = logg[i/2]+1;
    int B = 0.6*sqrt(N+K-1)+1;
    for (i = 0; i < N+K-1; i += B) {
        int e = min(N+K-1,i+B);
        fill(num,num+N,1);
        for (j = i; j < e; j++) {
            if ((a[j] >= 0) && (b[j] >= 0)) num[a[j]] = num[b[j]] = 0;
        }
        for (j = 0; j < N; j++) {
            if (num[j] == 0) vv.pb(j);
        }
        for (j = (int) edges.size()-1; j >= 0; j--) num[edges[j].first] = num[edges[j].second] = num[edges[j].first]+num[edges[j].second];
        for (j = i; j < e; j++) {
            if ((a[j] >= 0) && (b[j] >= 0)) edges.pb(mp(a[j],b[j]));
            else if (a[j] == -1) {
                int ans = num[b[j]];
                for (k = 0; k < vv.size(); k++) {
                    if (path(b[j],vv[k],j)) ans++;
                }
                printf("%d\n",ans);
            }
            else printf(path(-b[j]-1,a[j],j) ? "yes\n":"no\n");
        }
        vv.clear();
    }

    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int doDFS(int, int, int)':
servers.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                 for (k = 0; k < vv.size(); k++) {
      |                             ~~^~~~~~~~~~~
servers.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
servers.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
servers.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:86:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         else scanf("%d",&b[i]),a[i] = -1,b[i]--;
      |              ~~~~~^~~~~~~~~~~~

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5