oj.uz

Submission #25810

# Submission time Handle Problem Language Result Execution time Memory
25810 2017-06-24T08:03:09 Z 시제연(#1082) 전압 (JOI14_voltage) C++
100 / 100
 369 ms 29324 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];
bool visit[100100];
int tt, odd;
pii edg[200100];

int od[200100], ev[200100];

void dfs(int here, int col, int ep) {
    int i;
    s[here] = tt;
    ord[tt] = here;
    tt++;
    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++;
            int *p = ((color[here]==color[there])?od:ev);
            p[here]++; p[there]--;
            /*
            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]);
    }
    e[here] = tt;
}

int res;
void fdfs(int here, int p) {
    int i;
    visit[here] = true;
    for (i=0;i<lis[here].size();i++) {
        int there = lis[here][i];
        if (visit[there]) continue;
        fdfs(there,here);
        ev[here]+=ev[there];
        od[here]+=od[there];
    }
    if (od[here]==odd&&ev[here]==0&&p!=-1) res++;
}

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);
    }
    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]);
    }
    */
    for (i=0;i<n;i++) {
        if (visit[i]) continue;
        fdfs(i,-1);
    }
    for (i=0;i<m;i++) {
        if (rev[i]) {
            if (rev[i]==1&&odd==1) res++;
        }
    }
    printf("%d\n",res);

    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 dfs(int, int, int)':
voltage.cpp:60:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[here].size();i++) {
               ^
voltage.cpp: In function 'void fdfs(int, int)':
voltage.cpp:86: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:97:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j, k;
            ^
voltage.cpp:97:15: warning: unused variable 'k' [-Wunused-variable]
     int i, j, k;
               ^
voltage.cpp:101: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:104: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 15404 KB Output is correct
2 Correct 0 ms 15272 KB Output is correct
3 Correct 3 ms 15404 KB Output is correct
4 Correct 3 ms 15404 KB Output is correct
5 Correct 0 ms 15404 KB Output is correct
6 Correct 0 ms 15404 KB Output is correct
7 Correct 0 ms 15404 KB Output is correct
8 Correct 0 ms 15404 KB Output is correct
9 Correct 0 ms 15404 KB Output is correct
10 Correct 6 ms 15404 KB Output is correct
11 Correct 3 ms 15404 KB Output is correct
12 Correct 3 ms 15404 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 22564 KB Output is correct
2 Correct 156 ms 25868 KB Output is correct
3 Correct 96 ms 22564 KB Output is correct
4 Correct 106 ms 27476 KB Output is correct
5 Correct 9 ms 16064 KB Output is correct
6 Correct 129 ms 24008 KB Output is correct
7 Correct 183 ms 29164 KB Output is correct
8 Correct 196 ms 29164 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 22564 KB Output is correct
2 Correct 69 ms 29160 KB Output is correct
3 Correct 73 ms 29160 KB Output is correct
4 Correct 0 ms 15272 KB Output is correct
5 Correct 146 ms 24052 KB Output is correct
6 Correct 186 ms 21740 KB Output is correct
7 Correct 203 ms 24876 KB Output is correct
8 Correct 199 ms 26584 KB Output is correct
9 Correct 186 ms 26220 KB Output is correct
10 Correct 209 ms 24544 KB Output is correct
11 Correct 153 ms 21740 KB Output is correct
12 Correct 193 ms 23356 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 24104 KB Output is correct
2 Correct 126 ms 29164 KB Output is correct
3 Correct 6 ms 15272 KB Output is correct
4 Correct 209 ms 25804 KB Output is correct
5 Correct 203 ms 27084 KB Output is correct
6 Correct 193 ms 25612 KB Output is correct
7 Correct 323 ms 26884 KB Output is correct
8 Correct 319 ms 27708 KB Output is correct
9 Correct 299 ms 25320 KB Output is correct
10 Correct 369 ms 28488 KB Output is correct
11 Correct 276 ms 25568 KB Output is correct
12 Correct 296 ms 28516 KB Output is correct
13 Correct 273 ms 25772 KB Output is correct
14 Correct 316 ms 29324 KB Output is correct
15 Correct 336 ms 28560 KB Output is correct
16 Correct 269 ms 27992 KB Output is correct
17 Correct 323 ms 24944 KB Output is correct
18 Correct 269 ms 25672 KB Output is correct