oj.uz

Submission #581972

# Submission time Handle Problem Language Result Execution time Memory
581972 2022-06-23T08:57:01 Z 반딧불(#8365) 전압 (JOI14_voltage) C++14
100 / 100
 228 ms 31392 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct dat{
    int xl, xr, y, w, p;
    dat(){}
    dat(int xl, int xr, int y, int w, int p): xl(xl), xr(xr), y(y), w(w), p(p){}

    bool operator<(const dat &r)const{
        return y<r.y;
    }
};

struct Point{
    int x, y, w;
    Point(){}
    Point(int x, int y, int w): x(x), y(y), w(w){}
    bool operator<(const Point &r)const{
        return y<r.y;
    }
};

struct Fenwick{
    int n;
    int tree[100002];

    void init(int _n){
        n = _n;
        memset(tree, 0, sizeof(tree));
    }

    void add(int x, int y){
        while(x<=n){
            tree[x] += y;
            x += x&-x;
        }
    }

    int sum(int x){
        int ret = 0;
        while(x){
            ret += tree[x];
            x -= x&-x;
        }
        return ret;
    }

    int sum(int l, int r){
        if(l>r) return 0;
        return sum(r) - sum(l-1);
    }
} tree;

int n, m;
vector<pair<int, int> > link[200002];
int ex[200002], ey[200002];
bool usedInTree[200002];

vector<int> remEdge;
int ans;

bool visited[200002];
bool col[200002];
bool isWrong[200002];
int in[200002], out[200002], inCnt;
int depth[200002];

void tree_dfs(int x){
    visited[x] = 1;
    in[x] = ++inCnt;
    for(auto y: link[x]){
        if(visited[y.first]) continue;
        usedInTree[y.second] = true;
        col[y.first] = !col[x];
        depth[y.first] = depth[x]+1;
        tree_dfs(y.first);
    }
    out[x] = inCnt;
}

int sum[200002];
vector<dat> vecQuery;
vector<Point> vecPoint;

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        link[x].push_back(make_pair(y, i));
        link[y].push_back(make_pair(x, i));
        ex[i] = x, ey[i] = y;
    }

    for(int i=1; i<=n; i++){
        if(!visited[i]) tree_dfs(i);
    }
    for(int i=1; i<=m; i++) if(!usedInTree[i]) remEdge.push_back(i);
    for(int i=1; i<=n; i++) link[i].clear();
    for(int i=1; i<=m; i++){
        if(usedInTree[i]) link[ex[i]].push_back(make_pair(ey[i], i)), link[ey[i]].push_back(make_pair(ex[i], i));
        else{
            isWrong[i] = (col[ex[i]] == col[ey[i]]);
        }
    }
    if(count(isWrong+1, isWrong+m+1, true) == 1) ans++;

    int allGood = 0;
    for(int i=1; i<=m; i++){
        if(usedInTree[i]){ /// ���� ����
            int x = ex[i], p = ey[i];
            if(depth[x] < depth[p]) swap(x, p);
            int l = in[x], r = out[x];
            vecQuery.push_back(dat(l, r, r, -1, i));
            vecQuery.push_back(dat(l, r, n, 1, i));
            vecQuery.push_back(dat(1, l-1, l-1, -1, i));
            vecQuery.push_back(dat(1, l-1, r, 1, i));
        }
        else{
            if(isWrong[i]) allGood++;
            vecPoint.push_back(Point(min(in[ex[i]], in[ey[i]]), max(in[ex[i]], in[ey[i]]), isWrong[i]?1:-1));
        }
    }
    sort(vecQuery.begin(), vecQuery.end());
    sort(vecPoint.begin(), vecPoint.end());

    int pnt = 0;
    tree.init(n);
    for(dat query: vecQuery){
        while(pnt < (int)vecPoint.size() && vecPoint[pnt].y <= query.y){
            tree.add(vecPoint[pnt].x, vecPoint[pnt].w);
            pnt++;
        }
        sum[query.p] += tree.sum(query.xl, query.xr) * query.w;
    }

    for(int i=1; i<=m; i++){
        if(usedInTree[i]){
            if(sum[i] == allGood) ans++;
        }
    }
    printf("%d", ans);
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5716 KB Output is correct
2 Correct 3 ms 5460 KB Output is correct
3 Correct 3 ms 5460 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 4 ms 5716 KB Output is correct
6 Correct 4 ms 5748 KB Output is correct
7 Correct 4 ms 5716 KB Output is correct
8 Correct 4 ms 5644 KB Output is correct
9 Correct 3 ms 5716 KB Output is correct
10 Correct 4 ms 5716 KB Output is correct
11 Correct 4 ms 5716 KB Output is correct
12 Correct 4 ms 5716 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 22088 KB Output is correct
2 Correct 116 ms 24508 KB Output is correct
3 Correct 80 ms 22280 KB Output is correct
4 Correct 121 ms 25788 KB Output is correct
5 Correct 12 ms 7312 KB Output is correct
6 Correct 119 ms 23472 KB Output is correct
7 Correct 104 ms 27176 KB Output is correct
8 Correct 106 ms 27140 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 22024 KB Output is correct
2 Correct 71 ms 27048 KB Output is correct
3 Correct 72 ms 27020 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 102 ms 23256 KB Output is correct
6 Correct 110 ms 21308 KB Output is correct
7 Correct 122 ms 24128 KB Output is correct
8 Correct 122 ms 25068 KB Output is correct
9 Correct 125 ms 25112 KB Output is correct
10 Correct 117 ms 23764 KB Output is correct
11 Correct 140 ms 21508 KB Output is correct
12 Correct 132 ms 22912 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 24932 KB Output is correct
2 Correct 126 ms 30836 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 142 ms 25756 KB Output is correct
5 Correct 123 ms 26816 KB Output is correct
6 Correct 127 ms 25692 KB Output is correct
7 Correct 199 ms 30092 KB Output is correct
8 Correct 188 ms 30476 KB Output is correct
9 Correct 177 ms 28928 KB Output is correct
10 Correct 184 ms 31392 KB Output is correct
11 Correct 228 ms 28952 KB Output is correct
12 Correct 185 ms 31384 KB Output is correct
13 Correct 160 ms 28220 KB Output is correct
14 Correct 174 ms 31032 KB Output is correct
15 Correct 169 ms 30736 KB Output is correct
16 Correct 161 ms 29732 KB Output is correct
17 Correct 158 ms 30064 KB Output is correct
18 Correct 131 ms 29740 KB Output is correct