oj.uz

Submission #374050

# Submission time Handle Problem Language Result Execution time Memory
374050 2021-03-06T13:51:05 Z denkendoemeer Synchronization (JOI13_synchronization) C++14
100 / 100
 405 ms 32236 KB 
#include<bits/stdc++.h>
#define ll long long
const int inf=1e9;
using namespace std;
int x[100005],y[100005],z[100005],l[100005],in[100005],out[100005],c[100005],aib[100005];
vector<int>g[100005],s[100005];
int n,u,m,q;
void update(int poz,int val)
{
    while(poz<=n){
        aib[poz]+=val;
        poz+=poz&-poz;
    }
}
int query(int poz)
{
    int sum=0;
    while(poz){
        sum+=aib[poz];
        poz-=poz&-poz;
    }
    return sum;
}
void dfs(int nod,int t)
{
    s[nod].emplace_back(t);
    in[nod]=++u;
    int i;
    for(i=0;i<s[s[nod][i]].size();i++)
        s[nod].emplace_back(s[s[nod][i]][i]);
    for(auto &it:g[nod])
        if (it!=t)
            dfs(it,nod);
    out[nod]=u+1;
}
int calc(int nod)
{
    int x=query(in[nod]);
    int i;
    for(i=20;i>=0;i--)
        if (i<s[nod].size() && x==query(in[s[nod][i]]))
            nod=s[nod][i];
    return nod;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int i;
    scanf("%d%d%d",&n,&m,&q);
    for(i=1;i<n;i++){
        scanf("%d%d",&x[i],&y[i]);
        g[x[i]].emplace_back(y[i]);
        g[y[i]].emplace_back(x[i]);
    }
    dfs(1,0);
    for(i=1;i<n;i++)
        if (s[x[i]][0]==y[i])
            swap(x[i],y[i]);
    for(i=1;i<=n;i++)
        z[i]=1,update(in[i],1),update(out[i],-1);
    for(i=1;i<=m;i++){
        int a,b;
        scanf("%d",&a);
        b=calc(x[a]);
        if (c[a]==0){
            update(in[y[a]],-1);
            update(out[y[a]],1);
            z[b]+=z[y[a]]-l[a];
        }
        if (c[a]==1){
            update(in[y[a]],1);
            update(out[y[a]],-1);
            z[y[a]]=l[a]=z[b];
        }
        c[a]=1-c[a];
    }
    for(i=1;i<=n;i++)
        z[i]=z[calc(i)];
    for(i=1;i<=q;i++){
        int a;
        scanf("%d",&a);
        printf("%d\n",z[a]);
    }
return 0;
}

Compilation message

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(i=0;i<s[s[nod][i]].size();i++)
      |             ~^~~~~~~~~~~~~~~~~~~~
synchronization.cpp: In function 'int calc(int)':
synchronization.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         if (i<s[nod].size() && x==query(in[s[nod][i]]))
      |             ~^~~~~~~~~~~~~~
synchronization.cpp: In function 'int main()':
synchronization.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d%d%d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |         scanf("%d%d",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~
synchronization.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~
synchronization.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |         scanf("%d",&a);
      |         ~~~~~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 5 ms 5100 KB Output is correct
7 Correct 19 ms 6252 KB Output is correct
8 Correct 19 ms 6252 KB Output is correct
9 Correct 19 ms 6252 KB Output is correct
10 Correct 296 ms 18048 KB Output is correct
11 Correct 292 ms 18156 KB Output is correct
12 Correct 372 ms 31468 KB Output is correct
13 Correct 125 ms 16904 KB Output is correct
14 Correct 193 ms 17388 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 23788 KB Output is correct
2 Correct 144 ms 23532 KB Output is correct
3 Correct 202 ms 30444 KB Output is correct
4 Correct 199 ms 30572 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 4 ms 5100 KB Output is correct
6 Correct 6 ms 5228 KB Output is correct
7 Correct 27 ms 7532 KB Output is correct
8 Correct 405 ms 32236 KB Output is correct
9 Correct 395 ms 32236 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 32236 KB Output is correct
2 Correct 232 ms 31596 KB Output is correct
3 Correct 224 ms 31724 KB Output is correct
4 Correct 223 ms 31724 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5100 KB Output is correct
2 Correct 4 ms 5100 KB Output is correct
3 Correct 4 ms 5100 KB Output is correct
4 Correct 4 ms 5100 KB Output is correct
5 Correct 5 ms 5100 KB Output is correct
6 Correct 23 ms 6380 KB Output is correct
7 Correct 344 ms 19052 KB Output is correct
8 Correct 397 ms 32228 KB Output is correct
9 Correct 134 ms 17892 KB Output is correct
10 Correct 224 ms 18412 KB Output is correct
11 Correct 189 ms 25068 KB Output is correct
12 Correct 168 ms 24940 KB Output is correct
13 Correct 233 ms 31800 KB Output is correct