oj.uz

Submission #316988

# Submission time Handle Problem Language Result Execution time Memory
316988 2020-10-28T21:45:39 Z thecodingwizard Party (POI11_imp) C++11
81 / 100
 3000 ms 34032 KB 
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

bool adj[3000][3000];
int deg[3000];

int main() {
    int n, m; cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b; --a; --b;
        deg[a]++; deg[b]++;
        adj[a][b] = 1; adj[b][a] = 1;
    }

    vector<int> A;
    for (int i = 0; i < n; i++) {
        if (deg[i] >= n/3*2-1) {
            bool g = true;
            for (int x : A) {
                if (!adj[i][x]) g = false;
            }
            if (g) A.pb(i);
        }
        if ((int)A.size() == n/3) break;
    }

    if ((int)A.size() != n/3) {
        for (int v : A) deg[v] = -1;
        A.clear();
        for (int i = 0; i < n; i++) {
            if (deg[i] >= n/3*2-1) {
                bool g = true;
                for (int x : A) {
                    if (!adj[i][x]) g = false;
                }
                if (g) A.pb(i);
            }
            if ((int)A.size() == n/3) break;
        }
    }

    for (int x : A) cout << x+1 << " ";
    cout << endl;

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 640 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1024 KB Output is correct
2 Correct 79 ms 2552 KB Output is correct
3 Correct 78 ms 2468 KB Output is correct
4 Correct 79 ms 2552 KB Output is correct
5 Correct 79 ms 2552 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 2044 KB Output is correct
2 Correct 328 ms 6224 KB Output is correct
3 Correct 325 ms 6392 KB Output is correct
4 Correct 335 ms 6392 KB Output is correct
5 Correct 320 ms 6136 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3008 KB Output is correct
2 Correct 798 ms 7036 KB Output is correct
3 Correct 796 ms 12024 KB Output is correct
4 Correct 801 ms 12024 KB Output is correct
5 Correct 816 ms 12408 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 5048 KB Output is correct
2 Correct 1201 ms 7672 KB Output is correct
3 Correct 1207 ms 16408 KB Output is correct
4 Correct 1205 ms 16668 KB Output is correct
5 Correct 1203 ms 16572 KB Output is correct

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 7032 KB Output is correct
2 Correct 1518 ms 19924 KB Output is correct
3 Correct 1491 ms 19576 KB Output is correct
4 Correct 1493 ms 19960 KB Output is correct
5 Correct 1503 ms 19816 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1343 ms 8184 KB Output is correct
2 Correct 2029 ms 7384 KB Output is correct
3 Correct 2013 ms 25152 KB Output is correct
4 Correct 2029 ms 25336 KB Output is correct
5 Correct 2037 ms 25224 KB Output is correct

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1785 ms 9080 KB Output is correct
2 Correct 2427 ms 8060 KB Output is correct
3 Correct 2427 ms 29448 KB Output is correct
4 Correct 2463 ms 29728 KB Output is correct
5 Correct 2409 ms 29560 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2123 ms 8196 KB Output is correct
2 Correct 2867 ms 8824 KB Output is correct
3 Correct 2828 ms 33912 KB Output is correct
4 Correct 2849 ms 33916 KB Output is correct
5 Correct 2824 ms 34032 KB Output is correct

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2517 ms 8576 KB Output is correct
2 Execution timed out 3068 ms 9216 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3080 ms 10232 KB Time limit exceeded
2 Halted 0 ms 0 KB -