oj.uz

Submission #14710

# Submission time Handle Problem Language Result Execution time Memory
14710 2015-06-11T08:55:20 Z gs14004 우호 조약 체결 (JOI14_friends) C++14
35 / 100
 1000 ms 9812 KB 
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;

struct disj{
    int pa[100005], sz[100005];
    void init(int n){
        for(int i=1; i<=n; i++) pa[i] = i, sz[i] = 1;
    }
    int find(int x){
        if(pa[x] == x) return x;
        return pa[x] = find(pa[x]);
    }
    int size(int x){
        return sz[find(x)];
    }
    int uni(int p, int q){
        p = find(p);
        q = find(q);
        if(p == q) return 0;
        pa[q] = p;
        sz[p] += sz[q];
        return 1;
    }
}disj;

bool vis[100005];
int n,m;
vector<int> g[100005], ng[100005];
queue<int> q;

int main(){
    scanf("%d %d",&n,&m);
    disj.init(n);
    for (int i=0; i<m; i++) {
        int x,y;
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
    }
    for (int i=1; i<=n; i++) {
        for (int j=0; j+1<g[i].size(); j++) {
            disj.uni(g[i][j],g[i][j+1]);
        }
    }
    for (int i=1; i<=n; i++) {
        int pos = i;
        memset(vis,0,sizeof(vis));
        while (!vis[pos]) {
            vis[pos] = 1;
            if(!g[pos].empty() && disj.size(pos) != 1 && !vis[g[pos][0]]){
                disj.uni(g[pos][0],pos);
                pos = g[pos][0];
            }
        }
    }
    long long ret = 0;
    memset(vis,0,sizeof(vis));
    for (int i=1; i<=n; i++) {
        if(!vis[disj.find(i)]){
            vis[disj.find(i)] = 1;
            ret += 1ll * disj.size(i) * (disj.size(i) - 1);
        }
    }
    for (int i=1; i<=n; i++) {
        for (int &j : g[i]){
            if(disj.find(i) != disj.find(j)) ret++;
        }
    }
    printf("%lld",ret);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6780 KB Output is correct
2 Correct 0 ms 6780 KB Output is correct
3 Correct 0 ms 6780 KB Output is correct
4 Correct 2 ms 6780 KB Output is correct
5 Correct 0 ms 6780 KB Output is correct
6 Correct 0 ms 6780 KB Output is correct
7 Correct 0 ms 6780 KB Output is correct
8 Correct 0 ms 6780 KB Output is correct
9 Correct 0 ms 6780 KB Output is correct
10 Correct 2 ms 6780 KB Output is correct
11 Correct 0 ms 6780 KB Output is correct
12 Correct 0 ms 6780 KB Output is correct
13 Correct 2 ms 6780 KB Output is correct
14 Correct 0 ms 6780 KB Output is correct
15 Correct 0 ms 6780 KB Output is correct
16 Correct 0 ms 6780 KB Output is correct
17 Correct 0 ms 6780 KB Output is correct
18 Correct 0 ms 6780 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 6780 KB Output is correct
2 Correct 26 ms 6780 KB Output is correct
3 Correct 35 ms 6912 KB Output is correct
4 Correct 71 ms 7704 KB Output is correct
5 Correct 65 ms 7440 KB Output is correct
6 Correct 87 ms 8100 KB Output is correct
7 Correct 7 ms 6780 KB Output is correct
8 Correct 6 ms 6780 KB Output is correct
9 Correct 11 ms 6912 KB Output is correct
10 Correct 46 ms 7044 KB Output is correct
11 Correct 103 ms 8100 KB Output is correct
12 Correct 33 ms 6912 KB Output is correct
13 Correct 24 ms 6780 KB Output is correct
14 Correct 23 ms 6780 KB Output is correct
15 Correct 25 ms 6780 KB Output is correct
16 Correct 38 ms 7044 KB Output is correct
17 Correct 89 ms 7968 KB Output is correct
18 Correct 25 ms 6912 KB Output is correct
19 Correct 228 ms 6912 KB Output is correct
20 Correct 114 ms 8100 KB Output is correct
21 Correct 27 ms 6780 KB Output is correct
22 Correct 27 ms 6780 KB Output is correct
23 Correct 30 ms 6912 KB Output is correct
24 Correct 28 ms 6780 KB Output is correct
25 Correct 28 ms 6912 KB Output is correct
26 Correct 25 ms 6780 KB Output is correct
27 Correct 28 ms 6912 KB Output is correct
28 Correct 28 ms 6780 KB Output is correct

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 7836 KB Output is correct
2 Correct 615 ms 9552 KB Output is correct
3 Correct 595 ms 9552 KB Output is correct
4 Correct 511 ms 8628 KB Output is correct
5 Correct 500 ms 7968 KB Output is correct
6 Correct 395 ms 8760 KB Output is correct
7 Correct 556 ms 9552 KB Output is correct
8 Correct 572 ms 9552 KB Output is correct
9 Correct 523 ms 8760 KB Output is correct
10 Correct 532 ms 9156 KB Output is correct
11 Correct 609 ms 9552 KB Output is correct
12 Execution timed out 1000 ms 9812 KB Program timed out
13 Halted 0 ms 0 KB -