oj.uz

Submission #25811

# Submission time Handle Problem Language Result Execution time Memory
25811 2017-06-24T08:04:58 Z tlwpdus 전압 (JOI14_voltage) C++
100 / 100
 366 ms 25160 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;

int n, m;
vector<int> lis[100100];
vector<int> id[100100];
int color[100100];
int s[100100], e[100100], son[200100];
int rev[200100];
bool visit[100100];
int tt, odd;
int od[200100], ev[200100];

void dfs(int here, int col, int ep) {
    int i;
    s[here] = tt;
    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]--;
            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;

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

    return 0;
}

Compilation message

voltage.cpp: In function 'void dfs(int, int, int)':
voltage.cpp:22: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:43: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:56: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:59: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 11240 KB Output is correct
2 Correct 0 ms 11108 KB Output is correct
3 Correct 0 ms 11240 KB Output is correct
4 Correct 0 ms 11240 KB Output is correct
5 Correct 3 ms 11240 KB Output is correct
6 Correct 0 ms 11240 KB Output is correct
7 Correct 3 ms 11240 KB Output is correct
8 Correct 0 ms 11240 KB Output is correct
9 Correct 0 ms 11240 KB Output is correct
10 Correct 0 ms 11240 KB Output is correct
11 Correct 0 ms 11240 KB Output is correct
12 Correct 3 ms 11240 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 18400 KB Output is correct
2 Correct 193 ms 21696 KB Output is correct
3 Correct 96 ms 18400 KB Output is correct
4 Correct 129 ms 23312 KB Output is correct
5 Correct 6 ms 11900 KB Output is correct
6 Correct 176 ms 19844 KB Output is correct
7 Correct 189 ms 24996 KB Output is correct
8 Correct 176 ms 24996 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 18400 KB Output is correct
2 Correct 69 ms 24996 KB Output is correct
3 Correct 73 ms 24996 KB Output is correct
4 Correct 3 ms 11108 KB Output is correct
5 Correct 153 ms 19880 KB Output is correct
6 Correct 203 ms 17576 KB Output is correct
7 Correct 183 ms 20708 KB Output is correct
8 Correct 223 ms 22424 KB Output is correct
9 Correct 206 ms 22052 KB Output is correct
10 Correct 166 ms 20376 KB Output is correct
11 Correct 163 ms 17576 KB Output is correct
12 Correct 183 ms 19192 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 19940 KB Output is correct
2 Correct 93 ms 25000 KB Output is correct
3 Correct 0 ms 11108 KB Output is correct
4 Correct 189 ms 21636 KB Output is correct
5 Correct 199 ms 22924 KB Output is correct
6 Correct 213 ms 21448 KB Output is correct
7 Correct 263 ms 22720 KB Output is correct
8 Correct 296 ms 23548 KB Output is correct
9 Correct 329 ms 21152 KB Output is correct
10 Correct 266 ms 24320 KB Output is correct
11 Correct 343 ms 21404 KB Output is correct
12 Correct 366 ms 24352 KB Output is correct
13 Correct 263 ms 21608 KB Output is correct
14 Correct 286 ms 25160 KB Output is correct
15 Correct 303 ms 24400 KB Output is correct
16 Correct 313 ms 23832 KB Output is correct
17 Correct 239 ms 20784 KB Output is correct
18 Correct 229 ms 21512 KB Output is correct