oj.uz

Submission #130450

# Submission time Handle Problem Language Result Execution time Memory
130450 2019-07-15T08:25:06 Z 송준혁(#3152) Information (CEOI08_information) C++14
12 / 100
 1000 ms 17780 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, M, cnt;
int E[1010101];
vector<int> adj[2020];
vector<int> ans1, ans2;
bool chk[2020], Echk[1010101];

priority_queue<pii> PQ;

int main(){
    scanf("%d %d", &N, &M);
    for (int i=1; i<=M; i++){
        int x;
        scanf("%d %d", &x, &E[i]);
        adj[x].push_back(i);
    }
    E[0] = 1;
    for (int e=1; e<=100; e++){
        while (!PQ.empty()) PQ.pop();
        memset(chk, false, sizeof chk);
        memset(Echk, false, sizeof Echk);
        cnt = 0;
        ans1.clear();
        ans2.clear();
        PQ.push(pii(0, 0));
        while (cnt<N && !PQ.empty()){
            int t = PQ.top().second;
            PQ.pop();
            if (chk[E[t]]) continue;
            chk[E[t]] = true;
            ans1.push_back(t);
            Echk[t] = true;
            cnt++;
            for (int v : adj[E[t]]) PQ.push(pii(rand(), v));
        }
        if (cnt != N){
            puts("NONE");
            return 0;
        }

        Echk[0] = false;
        memset(chk, false, sizeof chk);
        cnt = 0;
        while (!PQ.empty()) PQ.pop();
        PQ.push(pii(0, 0));
        while (cnt<N){
            int t = PQ.top().second;
            PQ.pop();
            if (chk[E[t]] || Echk[t]) continue;
            chk[E[t]] = true;
            ans2.push_back(t);
            Echk[t] = true;
            cnt++;
            for (int v : adj[E[t]]) PQ.push(pii(rand(), v));
        }
        if (cnt == N){
            for (int i=1; i<(int)ans1.size(); i++) printf("%d ", ans1[i]);
            printf("\n");
            for (int i=1; i<(int)ans2.size(); i++) printf("%d ", ans2[i]);
            printf("\n");
            return 0;
        }
    }
    puts("NONE");
    return 0;
}

Compilation message

information.cpp: In function 'int main()':
information.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~~
information.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &x, &E[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 1272 KB Time limit exceeded

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 1400 KB Time limit exceeded

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 1400 KB Time limit exceeded

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1039 ms 1400 KB Time limit exceeded

Subtask #6
0 / 4.0

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

Subtask #7
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1320 KB Output is correct

Subtask #8
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1036 ms 1400 KB Time limit exceeded

Subtask #9
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 1400 KB Time limit exceeded

Subtask #10
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 1656 KB Time limit exceeded

Subtask #11
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 1400 KB Time limit exceeded

Subtask #12
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1400 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct

Subtask #13
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 1400 KB Time limit exceeded

Subtask #14
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 1400 KB Time limit exceeded

Subtask #15
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 2688 KB Time limit exceeded

Subtask #16
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 5228 KB Time limit exceeded

Subtask #17
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 3448 KB Time limit exceeded

Subtask #18
0 / 4.0

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

Subtask #19
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 1400 KB Time limit exceeded

Subtask #20
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 1400 KB Time limit exceeded

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 13580 KB Time limit exceeded

Subtask #22
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 17384 KB Time limit exceeded

Subtask #23
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 17780 KB Time limit exceeded

Subtask #24
0 / 5.0

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