oj.uz

Submission #559587

# Submission time Handle Problem Language Result Execution time Memory
559587 2022-05-10T08:42:43 Z stefantaga Senior Postmen (BOI14_postmen) C++14
100 / 100
 443 ms 47584 KB 
#include <bits/stdc++.h>

using namespace std;
struct wow
{
    int x,y;
}muchie[500005];
vector <pair <int,int>> v[500005];
int n,m,i,nr[500005],marc[500005],ok1,j,ok[500005];
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>muchie[i].x>>muchie[i].y;
        int x = muchie[i].x;
        int y = muchie[i].y;
        v[x].push_back({y,i});
        v[y].push_back({x,i});
    }
    int q;
    for (i=1;i<=n;i++)
    {
        q=0;
        nr[++q]=i;
        while (q)
        {
            int acum = nr[q];
            marc[acum]=1;
            ok1=0;
            while (v[acum].size())
            {
                int ind = v[acum].back().second;
                int nod = v[acum].back().first;
                v[acum].pop_back();
                if (ok[ind]==0)
                {
                    ok[ind]=1;
                    if (marc[nod]==1)
                    {
                        while (nr[q]!=nod)
                        {
                            marc[nr[q]]=0;
                            cout<<nr[q]<<" ";
                            q--;
                        }
                        cout<<nod<<'\n';
                    }
                    else
                    {
                        nr[++q]=nod;
                    }
                    ok1=1;
                    break;
                }
            }
            if (ok1==0)
            {
                q--;
            }
        }
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 8 ms 12196 KB Output is correct
5 Correct 7 ms 12116 KB Output is correct
6 Correct 9 ms 12244 KB Output is correct
7 Correct 10 ms 12780 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 32 ms 15584 KB Output is correct
10 Correct 8 ms 12116 KB Output is correct
11 Correct 8 ms 12104 KB Output is correct
12 Correct 36 ms 15852 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 7 ms 12288 KB Output is correct
7 Correct 10 ms 12756 KB Output is correct
8 Correct 7 ms 12116 KB Output is correct
9 Correct 42 ms 15676 KB Output is correct
10 Correct 8 ms 12116 KB Output is correct
11 Correct 7 ms 12124 KB Output is correct
12 Correct 35 ms 15884 KB Output is correct
13 Correct 55 ms 17700 KB Output is correct
14 Correct 56 ms 16992 KB Output is correct
15 Correct 45 ms 16504 KB Output is correct
16 Correct 61 ms 18844 KB Output is correct
17 Correct 60 ms 17872 KB Output is correct
18 Correct 65 ms 18148 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 12032 KB Output is correct
3 Correct 6 ms 12020 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 12296 KB Output is correct
7 Correct 11 ms 12760 KB Output is correct
8 Correct 8 ms 12200 KB Output is correct
9 Correct 35 ms 15620 KB Output is correct
10 Correct 8 ms 12116 KB Output is correct
11 Correct 7 ms 12164 KB Output is correct
12 Correct 34 ms 15964 KB Output is correct
13 Correct 68 ms 17708 KB Output is correct
14 Correct 56 ms 16972 KB Output is correct
15 Correct 43 ms 16488 KB Output is correct
16 Correct 79 ms 18792 KB Output is correct
17 Correct 54 ms 17884 KB Output is correct
18 Correct 55 ms 18124 KB Output is correct
19 Correct 400 ms 47584 KB Output is correct
20 Correct 394 ms 43708 KB Output is correct
21 Correct 334 ms 39856 KB Output is correct
22 Correct 403 ms 47548 KB Output is correct
23 Correct 138 ms 32588 KB Output is correct
24 Correct 443 ms 42400 KB Output is correct
25 Correct 365 ms 43920 KB Output is correct