oj.uz

Submission #922280

# Submission time Handle Problem Language Result Execution time Memory
922280 2024-02-05T11:07:50 Z AndrijaM Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 89116 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn=5e5+10;
int di[4]={1,-1,0,0};
int dj[4]={0,0,-1,1};

int n,m;
bool vis[maxn];
vector<pair<int,int>>g[maxn];
vector<int>path;

void dfs(int node)
{
    while(!g[node].empty())
    {
        auto ax=g[node].back();
        g[node].pop_back();
        if(vis[ax.second])continue;
        vis[ax.second]=1;
        dfs(ax.first);
    }
    path.push_back(node);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m;
    memset(vis,0,sizeof vis);
    for(int i=0;i<m;i++)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        g[x].push_back({y,i});
        g[y].push_back({x,i});
    }
    dfs(0);
    map<int,int>ma;
    vector<int>a;
    for(auto ax:path)
    {
        a.push_back(ax);
        ma[ax]++;
        if(ma[ax]==2)
        {
            cout<<ax+1<< " ";
            a.pop_back();
            while(a.back()!=ax)
            {
                cout<<a.back()+1<<" ";
                ma[a.back()]--;
                a.pop_back();
            }
            cout<<endl;
            ma[ax]=1;
        }
    }
    return 0;
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 12 ms 13916 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 46 ms 20940 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 5 ms 12892 KB Output is correct
12 Correct 51 ms 21456 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12632 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 6 ms 12892 KB Output is correct
5 Correct 4 ms 12616 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 11 ms 13916 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 45 ms 20948 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 5 ms 12892 KB Output is correct
12 Correct 51 ms 21264 KB Output is correct
13 Correct 68 ms 27560 KB Output is correct
14 Correct 87 ms 23708 KB Output is correct
15 Correct 100 ms 24776 KB Output is correct
16 Correct 69 ms 27648 KB Output is correct
17 Correct 107 ms 20944 KB Output is correct
18 Correct 86 ms 24780 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct
4 Correct 7 ms 12892 KB Output is correct
5 Correct 4 ms 12636 KB Output is correct
6 Correct 5 ms 12984 KB Output is correct
7 Correct 10 ms 14112 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 43 ms 20940 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 5 ms 12892 KB Output is correct
12 Correct 51 ms 21456 KB Output is correct
13 Correct 65 ms 27492 KB Output is correct
14 Correct 89 ms 23532 KB Output is correct
15 Correct 98 ms 24772 KB Output is correct
16 Correct 64 ms 27596 KB Output is correct
17 Correct 106 ms 20944 KB Output is correct
18 Correct 84 ms 24784 KB Output is correct
19 Execution timed out 508 ms 89116 KB Time limit exceeded
20 Halted 0 ms 0 KB -