oj.uz

Submission #25787

# Submission time Handle Problem Language Result Execution time Memory
25787 2017-06-24T06:49:36 Z 시제연(#1082) 전압 (JOI14_voltage) C++
45 / 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);
    }
    dfs(0,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
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 20020 KB Output is correct
2 Correct 159 ms 23184 KB Output is correct
3 Correct 109 ms 20020 KB Output is correct
4 Correct 156 ms 24992 KB Output is correct
5 Correct 13 ms 13608 KB Output is correct
6 Correct 146 ms 21280 KB Output is correct
7 Correct 176 ms 26344 KB Output is correct
8 Correct 196 ms 26340 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 20020 KB Output is correct
2 Correct 79 ms 26336 KB Output is correct
3 Correct 56 ms 26340 KB Output is correct
4 Correct 0 ms 12728 KB Output is correct
5 Correct 153 ms 21304 KB Output is correct
6 Correct 196 ms 19196 KB Output is correct
7 Correct 166 ms 22400 KB Output is correct
8 Correct 113 ms 24448 KB Output is correct
9 Correct 179 ms 23472 KB Output is correct
10 Correct 176 ms 22136 KB Output is correct
11 Correct 176 ms 19196 KB Output is correct
12 Correct 183 ms 20796 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 21560 KB Output is correct
2 Correct 103 ms 26336 KB Output is correct
3 Correct 3 ms 12728 KB Output is correct
4 Correct 293 ms 23004 KB Output is correct
5 Correct 276 ms 24548 KB Output is correct
6 Correct 509 ms 22920 KB Output is correct
7 Execution timed out 1000 ms 24284 KB Execution timed out
8 Halted 0 ms 0 KB -