oj.uz

Submission #382323

# Submission time Handle Problem Language Result Execution time Memory
382323 2021-03-27T05:43:53 Z davooddkareshki Game (IOI14_game) C++17
15 / 100
 2 ms 512 KB 
//#include "game.h"
#include<bits/stdc++.h>

typedef long long ll;
typedef long double ld;

using namespace std;

//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

const int inf = 1e9;
const int maxn = 1510;
const int mod = 1e9+7;

int n;
int pors[maxn][maxn], par[maxn], sz[maxn];

int get_par(int v)
{
    if(par[v] == -1) return v;
    return (par[v] = get_par(par[v]));
}

bool ans;
void dsu(int u, int v)
{
    u = get_par(u);
    v = get_par(v);
    if(sz[v] < sz[u]) swap(u,v);

    ans = 0;
    pors[u][v]++;
    pors[v][u]++;
    if(pors[u][v] == (sz[v] * sz[u]))
    {
        for(int i = 1; i <= n; i++)
        {
            if(par[i] == -1 && i != u && i != v)
            {
                pors[v][i] += pors[u][i];
                pors[i][v] += pors[u][i];
            }
        }

        ans = 1;
        sz[v] += sz[u];
        par[u] = v;
    }
}

void initialize(int N) {
    n = N;
    memset(par, -1, sizeof par);
    fill(sz, sz+maxn, 1);
}

int hasEdge(int u, int v) {
    dsu(u,v);
    return ans;
}
/*
signed main()
{
    //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    initialize(6);
    cout<< hasEdge(0,3) <<"\n";
    cout<< hasEdge(2,0) <<"\n";
    cout<< hasEdge(0,1) <<"\n";
    cout<< hasEdge(1,2) <<"\n";
    cout<< hasEdge(1,3) <<"\n";
    cout<< hasEdge(2,3) <<"\n";

}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 2 ms 492 KB Output is correct
28 Correct 2 ms 492 KB Output is correct
29 Incorrect 1 ms 492 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #3
0 / 58.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 492 KB Output is correct
26 Correct 1 ms 492 KB Output is correct
27 Correct 2 ms 492 KB Output is correct
28 Correct 1 ms 492 KB Output is correct
29 Incorrect 1 ms 492 KB Output isn't correct
30 Halted 0 ms 0 KB -