Submission #425846

#	Time	Username	Problem	Language	Result	Execution time	Memory
425846		duality	Inside information (BOI21_servers)	C++11	62.50 / 100	3568 ms	49388 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],num2 = 0;
vi order,child[120000];
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,depth[u] = d,disc[u] = num2++,order.pb(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);
    }
    fin[u] = num2;
    return 0;
}
int logn;
vpii edges;
int num[120000];
vi vv;
int lca(int u,int v) {
    int i;
    if (depth[u] < depth[v]) swap(u,v);
    for (i = logn-1; i >= 0; i--) {
        if ((parent[u][i] != -1) && (depth[parent[u][i]] >= depth[v])) u = parent[u][i];
    }
    if (u == v) return u;
    for (i = logn-1; i >= 0; i--) {
        if (parent[u][i] != parent[v][i]) u = parent[u][i],v = parent[v][i];
    }
    return parent[u][0];
}
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 i,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) < N; i++) {
        for (j = 0; j < N; j++) {
            if (parent[j][i-1] != -1) {
                parent[j][i] = parent[parent[j][i-1]][i-1];
                good[j][i] = (good[j][i-1] == good[parent[j][i-1]][i-1]) ? good[j][i-1]:0;
            }
            else parent[j][i] = -1;
        }
    }
    logn = i;
    int B = sqrt(N+K-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:18: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]
   18 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int path(int, int, int)':
servers.cpp:52:9: warning: unused variable 'i' [-Wunused-variable]
   52 |     int i,l = lca(u,v);
      |         ^
servers.cpp: In function 'int main()':
servers.cpp:128:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 for (k = 0; k < vv.size(); k++) {
      |                             ~~^~~~~~~~~~~
servers.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
servers.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
servers.cpp:81:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:87:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:90:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |         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: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5