oj.uz

Submission #781640

# Submission time Handle Problem Language Result Execution time Memory
781640 2023-07-13T09:05:28 Z Kritzan Naboj (COCI22_naboj) C++14
110 / 110
 634 ms 30136 KB 
#include <bits/stdc++.h>
using namespace std;

int n, m;
pair<int ,int> arr[500005];
vector<pair<int ,int> > v[200005];
int ways[200005];
bool vis[200005];
int pnt[200005];

stack<pair<int,int> > s;
queue<int> q;

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

    for(int i =1 ; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        arr[i] = {a, b};
        v[a].push_back({b, i});
        v[b].push_back({a, i});
        pnt[a]++;
        ways[a]++;
        ways[b]++;
    }

    memset(vis, 0, sizeof(vis));


    for(int i = 1; i <= n; i++) {
        if (ways[i] == pnt[i]) {
            s.push({i, 1});
            q.push(i);
            vis[i] = true;
        }
        else if (pnt[i] == 0){
            s.push({i, 0});
            q.push(i);
            vis[i] = true;
        }
    }

    while(!q.empty()) {
        int cur = q.front();
        q.pop();

        for(int i = 0; i < v[cur].size(); i++) {
            int nxt = v[cur][i].first;
            int idx = v[cur][i].second;
            ways[nxt]--;
            ways[cur]--;
            pnt[arr[idx].first]--;
            if (!vis[nxt] && pnt[nxt] == 0) {
                s.push({nxt, 0});
                q.push(nxt);
                vis[nxt] = true;
            }
            else if(!vis[nxt] && pnt[nxt] == ways[nxt]) {
                s.push({nxt, 1});
                q.push(nxt);
                vis[nxt] = true;
            }
        }


    }

    if (s.size() == n) {
        cout << n << endl;
        while(!s.empty()) {
            cout << s.top().first << " " << s.top().second << endl;
            s.pop();
        }
    }
    else {
        cout << -1 << endl;
        return 0;
    }

}

Compilation message

naboj.cpp: In function 'int main()':
naboj.cpp:48:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int i = 0; i < v[cur].size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~
naboj.cpp:69:18: warning: comparison of integer expressions of different signedness: 'std::stack<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   69 |     if (s.size() == n) {
      |         ~~~~~~~~~^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 2 ms 5204 KB Output is correct
9 Correct 2 ms 5204 KB Output is correct
10 Correct 3 ms 5152 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 2 ms 5204 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 20424 KB Output is correct
2 Correct 404 ms 20520 KB Output is correct
3 Correct 185 ms 13688 KB Output is correct
4 Correct 381 ms 20584 KB Output is correct
5 Correct 428 ms 20564 KB Output is correct
6 Correct 367 ms 20668 KB Output is correct
7 Correct 396 ms 20584 KB Output is correct
8 Correct 295 ms 17424 KB Output is correct
9 Correct 368 ms 20540 KB Output is correct
10 Correct 404 ms 20576 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Correct 2 ms 5204 KB Output is correct
8 Correct 2 ms 5204 KB Output is correct
9 Correct 2 ms 5204 KB Output is correct
10 Correct 3 ms 5152 KB Output is correct
11 Correct 3 ms 5204 KB Output is correct
12 Correct 2 ms 5204 KB Output is correct
13 Correct 3 ms 5204 KB Output is correct
14 Correct 3 ms 5204 KB Output is correct
15 Correct 382 ms 20424 KB Output is correct
16 Correct 404 ms 20520 KB Output is correct
17 Correct 185 ms 13688 KB Output is correct
18 Correct 381 ms 20584 KB Output is correct
19 Correct 428 ms 20564 KB Output is correct
20 Correct 367 ms 20668 KB Output is correct
21 Correct 396 ms 20584 KB Output is correct
22 Correct 295 ms 17424 KB Output is correct
23 Correct 368 ms 20540 KB Output is correct
24 Correct 404 ms 20576 KB Output is correct
25 Correct 332 ms 22776 KB Output is correct
26 Correct 256 ms 21640 KB Output is correct
27 Correct 319 ms 23524 KB Output is correct
28 Correct 408 ms 26692 KB Output is correct
29 Correct 194 ms 20124 KB Output is correct
30 Correct 420 ms 26480 KB Output is correct
31 Correct 46 ms 9320 KB Output is correct
32 Correct 400 ms 21120 KB Output is correct
33 Correct 617 ms 28916 KB Output is correct
34 Correct 402 ms 21772 KB Output is correct
35 Correct 634 ms 29100 KB Output is correct
36 Correct 397 ms 20952 KB Output is correct
37 Correct 566 ms 27416 KB Output is correct
38 Correct 545 ms 25080 KB Output is correct
39 Correct 580 ms 28852 KB Output is correct
40 Correct 611 ms 26452 KB Output is correct
41 Correct 529 ms 26156 KB Output is correct
42 Correct 632 ms 29952 KB Output is correct
43 Correct 411 ms 22660 KB Output is correct
44 Correct 604 ms 30136 KB Output is correct
45 Correct 439 ms 21724 KB Output is correct
46 Correct 551 ms 26440 KB Output is correct