oj.uz

Submission #412555

# Submission time Handle Problem Language Result Execution time Memory
412555 2021-05-27T06:08:58 Z 조영욱(#7650) Bread First Search (CCO21_day2problem2) C++17
0 / 25
 11 ms 14476 KB 
#include <bits/stdc++.h>
using namespace std;

vector<int> in[200001];
multiset<int> s;
const int sz=262144;
int seg[sz*2];
int lazy[sz*2];
vector<int> put[200001];
vector<int> er[200001];

void propagate(int node) {
    if (lazy[node]!=0) {
        seg[node]+=lazy[node];
        if (node<sz) {
            lazy[node*2]+=lazy[node];
            lazy[node*2+1]+=lazy[node];
        }
        lazy[node]=0;
    }
}

int sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    propagate(node);
    if (r<nodel||l>noder) {
        return 1e9;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return min(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int l,int r,int val,int node=1,int nodel=0,int noder=sz-1) {
    propagate(node);
    if (r<nodel||l>noder) {
        return;
    }
    if (l<=nodel&&noder<=r) {
        lazy[node]+=val;
        propagate(node);
        return;
    }
    int mid=(nodel+noder)/2;
    update(l,r,val,node*2,nodel,mid);
    update(l,r,val,node*2+1,mid+1,noder);
    seg[node]=min(seg[node*2],seg[node*2+1]);
}

int main(void) {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=0;i<m;i++) {
        int a,b;
        scanf("%d %d",&a,&b);
        if (a>b) {
            swap(a,b);
        }
        in[b].push_back(a);
        put[a].push_back(a);
        er[b].push_back(a);
    }
    for(int i=1;i<=n;i++) {
        sort(in[i].begin(),in[i].end());
    }
    for(int i=1;i<=n;i++) {
        int mini;
        if (in[i].empty()) {
            mini=i-1;
        }
        else {
            mini=in[i][0]-1;
        }
        if (i!=1)
            update(0,mini,1);
        for(int j=0;j<put[i].size();j++) {
            s.insert(put[i][j]);
        }
        for(int j=0;j<er[i].size();j++) {
            s.erase(s.find(er[i][j]));
        }
        int en;
        if (!s.empty()) {
            en=(*s.begin())-1;
        }
        else {
            en=i-1;
        }
        int val=sum(0,min(en,i-1));
        update(i,i,val);
    }
    printf("%d",sum(n,n));
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for(int j=0;j<put[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~
Main.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<er[i].size();j++) {
      |                     ~^~~~~~~~~~~~~
Main.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 11 ms 14336 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14476 KB Output is correct
6 Correct 10 ms 14412 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Incorrect 9 ms 14408 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 11 ms 14336 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14476 KB Output is correct
6 Correct 10 ms 14412 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Incorrect 9 ms 14408 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14412 KB Output is correct
2 Correct 11 ms 14336 KB Output is correct
3 Correct 9 ms 14412 KB Output is correct
4 Correct 9 ms 14412 KB Output is correct
5 Correct 9 ms 14476 KB Output is correct
6 Correct 10 ms 14412 KB Output is correct
7 Correct 10 ms 14412 KB Output is correct
8 Correct 10 ms 14412 KB Output is correct
9 Incorrect 9 ms 14408 KB Output isn't correct
10 Halted 0 ms 0 KB -