oj.uz

Submission #816228

# Submission time Handle Problem Language Result Execution time Memory
816228 2023-08-09T04:30:55 Z 이동현(#10127) Marshmallow Molecules (CCO19_day2problem2) C++17
10 / 25
 4000 ms 11368 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> r(n), l(n);
    for(int i = 0; i < m; ++i){
        int x, y;
        cin >> x >> y;
        --x, --y;
        r[x].push_back(y);
        l[y].push_back(x);
    }

    int ans = 0;
    for(int i = 0; i < n; ++i){
        vector<int> chk(n);

        queue<int> que;
        que.push(i);
        chk[i] = 1;
        while(!que.empty()){
            int now = que.front();
            que.pop();

            for(auto&nxt:r[now]){
                if(!chk[nxt] && nxt <= i){
                    chk[nxt] = 1;
                    que.push(nxt);
                }
            }
            for(auto&nxt:l[now]){
                if(!chk[nxt] && nxt <= i){
                    chk[nxt] = 1;
                    que.push(nxt);
                }
            }
        }

        for(int j = 0; j <= i; ++j){
            if(!chk[j]) continue;

            for(auto&nxt:r[j]){
                if(nxt <= i) continue;
                ans += !chk[nxt];
                chk[nxt] = 1;
            }
        }
    }

    cout << ans << '\n';
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 388 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 408 KB Output is correct
13 Correct 3 ms 420 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 388 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 408 KB Output is correct
13 Correct 3 ms 420 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3380 ms 3444 KB Output is correct
17 Correct 3604 ms 3204 KB Output is correct
18 Correct 3398 ms 3236 KB Output is correct
19 Correct 3232 ms 3464 KB Output is correct
20 Correct 3213 ms 3380 KB Output is correct
21 Correct 239 ms 812 KB Output is correct
22 Correct 3238 ms 3564 KB Output is correct
23 Correct 3307 ms 3192 KB Output is correct
24 Correct 3337 ms 3252 KB Output is correct
25 Correct 3340 ms 3348 KB Output is correct
26 Correct 3246 ms 3372 KB Output is correct
27 Correct 236 ms 804 KB Output is correct

Subtask #3
0 / 5.0

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

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 ms 388 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 3 ms 408 KB Output is correct
13 Correct 3 ms 420 KB Output is correct
14 Correct 2 ms 340 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 3380 ms 3444 KB Output is correct
17 Correct 3604 ms 3204 KB Output is correct
18 Correct 3398 ms 3236 KB Output is correct
19 Correct 3232 ms 3464 KB Output is correct
20 Correct 3213 ms 3380 KB Output is correct
21 Correct 239 ms 812 KB Output is correct
22 Correct 3238 ms 3564 KB Output is correct
23 Correct 3307 ms 3192 KB Output is correct
24 Correct 3337 ms 3252 KB Output is correct
25 Correct 3340 ms 3348 KB Output is correct
26 Correct 3246 ms 3372 KB Output is correct
27 Correct 236 ms 804 KB Output is correct
28 Execution timed out 4053 ms 11368 KB Time limit exceeded
29 Halted 0 ms 0 KB -