oj.uz

Submission #603662

# Submission time Handle Problem Language Result Execution time Memory
603662 2022-07-24T09:26:02 Z 박상훈(#8426) Synchronization (JOI13_synchronization) C++17
30 / 100
 193 ms 12624 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
struct Edge{
    int v, l, r;
    Edge(){}
    Edge(int _v, int _l, int _r): v(_v), l(_l), r(_r) {}
    bool operator<(const Edge &E)const{
        return r > E.r;
    }
};
int A[100100], B[100100], on[100100], prv[100100], ans;
vector<Edge> adj[100100];
bool visited[100100];


struct Node{
    int l, r, ansl, ansr;
    Node(){}
    Node(int _l, int _r, int _ansl, int _ansr): l(_l), r(_r), ansl(_ansl), ansr(_ansr) {}
};
struct Seg{
    Node tree[400400], lazy[400400];
    void init(int i, int l, int r){
        if (l==r) tree[i] = Node(l, l, l, l);
        lazy[i] = Node(-1, -1, -1, -1);
        if (l==r) return;
        int m = (l+r)>>1;
        init(i<<1, l, m); init(i<<1|1, m+1, r);
    }
    void propagate(int i, int l, int r){
        if (lazy[i].l==-1) return;
        tree[i] = lazy[i];
        if (l!=r){
            lazy[i<<1] = lazy[i];
            lazy[i<<1|1] = lazy[i];

        }
        lazy[i] = Node(-1, -1, -1, -1);
    }

    void update(int i, int l, int r, int s, int e, int L, int R, int AL, int AR){
        propagate(i, l, r);
        if (r<s || e<l) return;
        if (s<=l && r<=e){
            lazy[i] = Node(L, R, AL, AR);
            propagate(i, l, r);
            return;
        }
        int m = (l+r)>>1;
        update(i<<1, l, m, s, e, L, R, AL, AR); update(i<<1|1, m+1, r, s, e, L, R, AL, AR);
    }
    Node query(int i, int l, int r, int s){
        propagate(i, l, r);
        if (l==r) return tree[i];
        int m = (l+r)>>1;
        if (s<=m) return query(i<<1, l, m, s);
        return query(i<<1|1, m+1, r, s);
    }
}tree;

void dfs(int s, int t, int pa = -1){
    if (visited[s]) return;
    ans++;
    visited[s] = 1;
    sort(adj[s].begin(), adj[s].end());
    for (auto &[v, l, r]:adj[s]) if (v!=pa){
        if (l<=t){
            dfs(v, min(r, t), s);
        }
    }
}

int main(){
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    for (int i=1;i<=n-1;i++){
        scanf("%d %d", A+i, B+i);
    }

    tree.init(1, 1, n);

    for (int i=1;i<=m;i++){
        int x;
        scanf("%d", &x);

        if (!on[x]){
            auto Nl = tree.query(1, 1, n, x), Nr = tree.query(1, 1, n, x+1);

            int tl = min(Nl.ansl, Nr.ansl), tr = max(Nl.ansr, Nr.ansr);

            tree.update(1, 1, n, Nl.l, Nr.r, Nl.l, Nr.r, tl, tr);
        }

        else{
            auto N = tree.query(1, 1, n, x);
            tree.update(1, 1, n, N.l, x, N.l, x, N.ansl, N.ansr);
            tree.update(1, 1, n, x+1, N.r, x+1, N.r, N.ansl, N.ansr);
        }
        on[x] ^= 1;
    }

    for (int i=1;i<=q;i++){
        int x;
        scanf("%d", &x);
        auto N = tree.query(1, 1, n, x);
        printf("%d\n", N.ansr-N.ansl+1);
    }
    return 0;
}

Compilation message

synchronization.cpp: In function 'int main()':
synchronization.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%d %d", A+i, B+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
synchronization.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~
synchronization.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%d", &x);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 120 ms 11976 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 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 3 ms 2644 KB Output is correct
7 Correct 16 ms 3800 KB Output is correct
8 Correct 176 ms 12000 KB Output is correct
9 Correct 177 ms 11916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 12036 KB Output is correct
2 Correct 117 ms 12624 KB Output is correct
3 Correct 121 ms 12592 KB Output is correct
4 Correct 106 ms 12612 KB Output is correct

Subtask #5
0 / 40.0

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