oj.uz

Submission #25788

# Submission time Handle Problem Language Result Execution time Memory
25788 2017-06-24T06:53:04 Z 시제연(#1082) 전압 (JOI14_voltage) C++
55 / 100
 1000 ms 26344 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

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

int n, m;
vector<int> lis[100100];
vector<int> id[100100];

vector<int> st, et;
int color[100100];
int par[100100];
int ps[2][100100];
int s[100100], e[100100];
int tt, odd;

int od[200100], ev[200100];
void dfs(int here, int col, int p, int ep) {
    int i, j;
    s[here] = tt++;
    par[here] = p;
    color[here] = col;
    st.push_back(here);
    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;
            int *p = ((color[here]==color[there])?od:ev);
            if (color[here]==color[there]) odd++;
            p[id[here][i]]++;
            for (j=(int)st.size()-1;st[j]!=there;j--) p[et[j-1]]++;
            continue;
        }
        et.push_back(id[here][i]);
        dfs(there,3-col,here,id[here][i]);
        et.pop_back();
    }
    st.pop_back();
    e[here] = tt;
}

int main() {
    int i, j;

    //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);
    }
    for (i=0;i<n;i++) {
        if (color[i]) continue;
        dfs(i,1,-1,-1);
    }
    int cnt = 0;
    for (i=0;i<m;i++) {
        //printf("%d %d\n",od[i],ev[i]);
        if (od[i]==odd&&ev[i]==0) cnt++;
    }
    printf("%d\n",cnt);

    return 0;
}

Compilation message

voltage.cpp:9:15: warning: non-static data member initializers only available with -std=c++11 or -std=gnu++11
     int key = 131072;
               ^
voltage.cpp: In member function 'int idxtree::getv(int)':
voltage.cpp:27:16: warning: statement has no effect [-Wunused-value]
             idx>>1;
                ^
voltage.cpp: In function 'void dfs(int, int, int, int)':
voltage.cpp:51: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:73:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
voltage.cpp:77: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:80: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 6 ms 12860 KB Output is correct
2 Correct 0 ms 12728 KB Output is correct
3 Correct 3 ms 12860 KB Output is correct
4 Correct 3 ms 12860 KB Output is correct
5 Correct 3 ms 12860 KB Output is correct
6 Correct 0 ms 12860 KB Output is correct
7 Correct 0 ms 12860 KB Output is correct
8 Correct 0 ms 12860 KB Output is correct
9 Correct 3 ms 12860 KB Output is correct
10 Correct 6 ms 12860 KB Output is correct
11 Correct 0 ms 12860 KB Output is correct
12 Correct 3 ms 12860 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 20020 KB Output is correct
2 Correct 173 ms 23184 KB Output is correct
3 Correct 103 ms 20020 KB Output is correct
4 Correct 103 ms 24992 KB Output is correct
5 Correct 13 ms 13608 KB Output is correct
6 Correct 193 ms 21280 KB Output is correct
7 Correct 183 ms 26340 KB Output is correct
8 Correct 103 ms 26344 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 20020 KB Output is correct
2 Correct 93 ms 26340 KB Output is correct
3 Correct 66 ms 26340 KB Output is correct
4 Correct 0 ms 12728 KB Output is correct
5 Correct 149 ms 21308 KB Output is correct
6 Correct 189 ms 19196 KB Output is correct
7 Correct 173 ms 22396 KB Output is correct
8 Correct 186 ms 24452 KB Output is correct
9 Correct 189 ms 23472 KB Output is correct
10 Correct 196 ms 22132 KB Output is correct
11 Correct 176 ms 19196 KB Output is correct
12 Correct 169 ms 20792 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 21560 KB Output is correct
2 Correct 116 ms 26336 KB Output is correct
3 Correct 0 ms 12728 KB Output is correct
4 Correct 299 ms 23004 KB Output is correct
5 Correct 263 ms 24548 KB Output is correct
6 Correct 513 ms 22916 KB Output is correct
7 Execution timed out 1000 ms 24288 KB Execution timed out
8 Halted 0 ms 0 KB -