Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学暑期课《ACM/ICPC竞赛训练》面向全球招生!

Re:几组测试数据

Posted by 08220420 at 2009-08-12 18:20:29 on Problem 1182
In Reply To:几组测试数据 Posted by:wanghaishanren at 2008-04-30 19:40:11
上面的都过了,vijos也ac了,交上去还WA,无语。。。。。那个大牛帮下
#include<iostream>
using namespace std;
int fa[500001], flag[500001];

void Initset(int n) {
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
        flag[i] = 0;
    }
}

int find(int x) {
    int t = fa[x];
    if (fa[x] != x) {
        fa[x] = find(fa[x]);
        flag[x] = (flag[x] + flag[t] + 1) % 3 - 1;
    }
    return fa[x];
}

int unin(int a, int x, int y) {
    int m = find(x), n = find(y);
    if (m == n) {
        if ((flag[x] - flag[y] + 3) % 3 != a - 1)return 1;
    } else fa[m] = n, flag[m] = (flag[y] - flag[x] + a) % 3 - 1;
    return 0;
}

int main() {
    int n, k, a, x, y, re;
    while (cin >> n >> k) {
        Initset(n);
        re = 0;
        while (k--) {
            cin >> a >> x >> y;
            if (x > n || y > n || (a == 2 && x == y) || unin(a, x, y)) re++;
        }
        cout << re << endl;
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator