Submission #425828

#	Time	Username	Problem	Language	Result	Execution time	Memory
425828		duality	Inside information (BOI21_servers)	C++11	65 / 100	3578 ms	38540 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];
int doDFS(int u,int p,int d) {
    int i;
    parent[u][0] = p,depth[u] = d;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i].first;
        if (v != p) pe[v] = adjList[u][i].second,doDFS(v,u,d+1);
    }
    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 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;
        for (i = logn-1; i >= 0; i--) {
            if ((parent[v][i] != -1) && (depth[parent[v][i]] > depth[l])) {
                if (good[v][i] != -1) return 0;
                else v = parent[v][i];
            }
        }
        return 1;
    }
    else if (l == v) {
        for (i = logn-1; i >= 0; i--) {
            if ((parent[u][i] != -1) && (depth[parent[u][i]] > depth[l])) {
                if (good[u][i] != 1) return 0;
                else u = parent[u][i];
            }
        }
        if (pe[u] > c) return 0;
        return 1;
    }
    else {
        if (pe[v] > c) return 0;
        for (i = logn-1; i >= 0; i--) {
            if ((parent[u][i] != -1) && (depth[parent[u][i]] > depth[l])) {
                if (good[u][i] != 1) return 0;
                else u = parent[u][i];
            }
        }
        for (i = logn-1; i >= 0; i--) {
            if ((parent[v][i] != -1) && (depth[parent[v][i]] > depth[l])) {
                if (good[v][i] != -1) return 0;
                else v = parent[v][i];
            }
        }
        return pe[u] < pe[v];
    }
}
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; (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:16: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]
   16 |     for (i = 0; i < adjList[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:129:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                 for (k = 0; k < vv.size(); k++) {
      |                             ~~^~~~~~~~~~~
servers.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |     scanf("%d %d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~~
servers.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |         scanf(" %c",&c);
      |         ~~~~~^~~~~~~~~~
servers.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:92:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |             scanf("%d %d",&a[i],&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~
servers.cpp:95:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         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: 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