oj.uz

Submission #603649

# Submission time Handle Problem Language Result Execution time Memory
603649 2022-07-24T09:22:40 Z 조영욱(#8429) Synchronization (JOI13_synchronization) C++17
30 / 100
 256 ms 42736 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m,q;
typedef pair<int,int> P;
P edge[100000];
int ont[100000];
typedef pair<int,int> P;
vector<P> adj[100001];
int dp[500000];
int cnt=0;
int ind[100001];
typedef pair<P,int> Pi;
vector<int> put[200001];
vector<int> er[200001];
set<int> s;
P le[500000];
P ri[500000];
int ldp[500000];
int rdp[500000];
int pos[500000];

int lv(int now) {
    if (ldp[now]!=-1) {
        return ldp[now];
    }
    if (le[now].first==-1) {
        return ldp[now]=le[now].second;
    }
    return ldp[now]=lv(le[now].first);
}

int rv(int now) {
    if (rdp[now]!=-1) {
        return rdp[now];
    }
    if (ri[now].first==-1) {
        return rdp[now]=ri[now].second;
    }
    return rdp[now]=rv(ri[now].first);
}

int main(void) {
    scanf("%d %d %d",&n,&m,&q);
    for(int i=1;i<n;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        a--;
        b--;
        adj[a].push_back(P(b,i));
        adj[b].push_back(P(a,i));
        edge[i]=P(a,b);
    }
    memset(ont,-1,sizeof(ont));
    for(int i=0;i<m;i++) {
        int x;
        scanf("%d",&x);
        if (ont[x]!=-1) {
            //s[x].insert(P(ont[x],i-1));
            ont[x]=-1;
            er[i-1].push_back(x);
        }
        else {
            ont[x]=i;
            put[i].push_back(x);
        }
    }
    for(int i=1;i<n;i++) {
        if (ont[i]!=-1) {
            //s[i].insert(P(ont[i],m-1));
            er[m-1].push_back(i);
        }
        s.insert(i);
    }
    memset(dp,-1,sizeof(dp));
    memset(ind,-1,sizeof(ind));
    memset(le,-1,sizeof(le));
    memset(ri,-1,sizeof(ri));
    for(int i=0;i<m;i++) {
        for(int j=0;j<put[i].size();j++) {
            int now=put[i][j];
            ind[now]=cnt;
            pos[ind[now]]=now;
            cnt++;
            s.erase(now);
        }
        for(int j=0;j<er[i].size();j++) {
            int now=er[i][j];
            int idx=ind[now];
            s.insert(now);
            auto iter=s.lower_bound(now);
            if (iter!=s.begin()) {
                iter--;
                le[idx]=P(ind[(*iter)],-1);
                if (ind[(*iter)]==-1) {
                    le[idx].second=(*iter)+1;
                }
                iter++;
            }
            else {
                le[idx]=P(-1,1);
            }
            iter++;
            if (iter!=s.end()) {
                ri[idx]=P(ind[(*iter)],-1);
                if (ind[(*iter)]==-1) {
                    ri[idx].second=(*iter)-1;
                }
            }
            else {
                ri[idx]=P(-1,n-1);
            }
        }
    }
    memset(ldp,-1,sizeof(ldp));
    memset(rdp,-1,sizeof(rdp));
    for(int i=0;i<q;i++) {
        int st;
        scanf("%d",&st);
        st--;
        int ret=0;
        if (ind[st]!=-1) {
            int idx=ind[st];
            idx=lv(idx);
            ret+=st-idx+1;
        }
        if (ind[st+1]!=-1) {
            int idx=ind[st+1];
            idx=rv(idx);
            ret+=idx-st;
        }
        printf("%d\n",ret+1);
    }
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:77:28: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'P' {aka 'struct std::pair<int, int>'} with no trivial copy-assignment [-Wclass-memaccess]
   77 |     memset(le,-1,sizeof(le));
      |                            ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from synchronization.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'P' {aka 'struct std::pair<int, int>'} declared here
  211 |     struct pair
      |            ^~~~
synchronization.cpp:78:28: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'P' {aka 'struct std::pair<int, int>'} with no trivial copy-assignment [-Wclass-memaccess]
   78 |     memset(ri,-1,sizeof(ri));
      |                            ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from synchronization.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'P' {aka 'struct std::pair<int, int>'} declared here
  211 |     struct pair
      |            ^~~~
synchronization.cpp:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int j=0;j<put[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
synchronization.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int j=0;j<er[i].size();j++) {
      |                     ~^~~~~~~~~~~~~
synchronization.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d %d %d",&n,&m,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
synchronization.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d",&x);
      |         ~~~~~^~~~~~~~~
synchronization.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         scanf("%d",&st);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 26452 KB Output is correct
2 Incorrect 14 ms 26452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 42736 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 26488 KB Output is correct
2 Correct 13 ms 26452 KB Output is correct
3 Correct 12 ms 26556 KB Output is correct
4 Correct 12 ms 26444 KB Output is correct
5 Correct 13 ms 26488 KB Output is correct
6 Correct 14 ms 26616 KB Output is correct
7 Correct 28 ms 28104 KB Output is correct
8 Correct 211 ms 42196 KB Output is correct
9 Correct 202 ms 42272 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 42196 KB Output is correct
2 Correct 123 ms 39536 KB Output is correct
3 Correct 129 ms 39616 KB Output is correct
4 Correct 160 ms 39644 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 26452 KB Output isn't correct
2 Halted 0 ms 0 KB -