oj.uz

Submission #25799

# Submission time Handle Problem Language Result Execution time Memory
25799 2017-06-24T07:37:27 Z 시제연(#1082) 전압 (JOI14_voltage) C++
0 / 100
 266 ms 27504 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

struct event {
    int x, s, e, val;
    event(int x, int s, int e, int v):x(x),s(s),e(e),val(v){}
    bool operator < (const event &A) const {return x<A.x;}
};

struct idxtree {
    int tree[270000];
    int key = 131072;
    idxtree() {
        int i;
        for (i=0;i<key*2;i++) tree[i] = 0;
    }
    void upd(int idx,int val) {
        idx+=key;
        while(idx>0) {
            tree[idx]+=val;
            idx>>=1;
        }
    }
    int getv(int s, int e) {
        int sum = 0;
        s+=key; e+=key;
        while(s<=e) {
            if (s&1) sum+=tree[s++];
            if (~e&1) sum+=tree[e--];
            s>>=1;e>>=1;
        }
        return sum;
    }
} ovt, evt;

int n, m;
vector<int> lis[100100];
vector<int> id[100100];
vector<event> eve, ove;
int color[100100];
int s[100100], e[100100], son[200100];
bool ok[100100];
int rev[200100];
int ord[100100];
int tt, odd;
pii edg[200100];

int od[200100], ev[200100];

void idfs(int here) {
    int i;
    s[here] = tt;
    ord[tt] = here;
    tt++;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (~s[there]) continue;
        idfs(there);
    }
    e[here] = tt;
}

void dfs(int here, int col, int ep) {
    int i;
    color[here] = col;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (id[here][i]==ep) continue;
        if (color[there]) {
            if (s[there]>s[here]) continue;
            rev[id[here][i]] = ((color[here]==color[there])?1:2);
            if (color[here]==color[there]) odd++;
            idxtree &it = ((color[here]==color[there])?ovt:evt);
            it.upd(s[here],1);
            it.upd(s[there],-1);
            /*
            vector<event> &v = ((color[here]==color[there])?ove:eve);
            v.push_back(event(s[there],e[here],e[there],1));
            v.push_back(event(s[here],e[here],e[there],-1));
            */
            continue;
        }
        son[id[here][i]] = there;
        dfs(there,3-col,id[here][i]);
    }
}

int main() {
    int i, j, k;

    //freopen("input","r",stdin);

    scanf("%d%d",&n,&m);
    for (i=0;i<m;i++) {
        int a, b;
        scanf("%d%d",&a,&b);
        a--;b--;
        lis[a].push_back(b);
        id[a].push_back(i);
        lis[b].push_back(a);
        id[b].push_back(i);
        edg[i] = pii(a,b);
    }
    memset(s,-1,sizeof(s));
    for (i=0;i<n;i++) {
        if (~s[i]) continue;
        idfs(i);
    }
    for (i=0;i<n;i++) {
        if (color[i]) continue;
        dfs(i,1,-1);
    }
    /*
    sort(eve.begin(),eve.end());
    sort(ove.begin(),ove.end());
    j=k=0;
    for (i=0;i<tt;i++) {
        for (;j<eve.size()&&eve[j].x==i;j++) evt.upd(eve[j].s,eve[j].e,eve[j].val);
        for (;k<ove.size()&&ove[k].x==i;k++) ovt.upd(ove[j].s,ove[j].e,ove[j].val);
        if (evt.getv(e[ord[i]])==0&&ovt.getv(e[ord[i]])==odd) ok[ord[i]] = true;
    }
    for (i=0;i<n;i++) {
        printf("%d : %d\n",i+1,ok[i]);
    }
    */
    int cnt = 0;
    for (i=0;i<m;i++) {
        if (rev[i]) {
            if (rev[i]==1&&odd==1) cnt++;
        }
        else {
            int so = son[i];
            if (evt.getv(s[so],e[so])==0&&ovt.getv(s[so],e[so])==odd) cnt++;
        }
    }
    printf("%d\n",cnt);

    return 0;
}

Compilation message

voltage.cpp:15:15: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     int key = 131072;
               ^
voltage.cpp: In function 'void idfs(int)':
voltage.cpp:58:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
voltage.cpp: In function 'void dfs(int, int, int)':
voltage.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
voltage.cpp: In function 'int main()':
voltage.cpp:92:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, k;
            ^
voltage.cpp:92:15: warning: unused variable 'k' [-Wunused-variable]
     int i, j, k;
               ^
voltage.cpp:96:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
                        ^
voltage.cpp:99:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a,&b);
                            ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 22464 KB Output is correct
2 Correct 99 ms 27504 KB Output is correct
3 Correct 73 ms 27500 KB Output is correct
4 Correct 3 ms 15172 KB Output is correct
5 Correct 173 ms 23172 KB Output is correct
6 Correct 166 ms 21640 KB Output is correct
7 Incorrect 246 ms 24068 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 24004 KB Output is correct
2 Correct 106 ms 27500 KB Output is correct
3 Correct 0 ms 15172 KB Output is correct
4 Incorrect 266 ms 24836 KB Output isn't correct
5 Halted 0 ms 0 KB -