oj.uz

Submission #722677

# Submission time Handle Problem Language Result Execution time Memory
722677 2023-04-12T15:00:09 Z mnbvcxz123 Senior Postmen (BOI14_postmen) C++17
100 / 100
 439 ms 97612 KB 
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ar=array<int,2>;
constexpr int MAXN=5e5+1;
int n,m,nxt[MAXN],cyc;
bool vis[MAXN],trav[MAXN];
vector<ar>g[MAXN];
vector<int>res;

void dfs(int v){
        vis[v]=1;
        while(nxt[v]<g[v].size()){
                auto i=g[v][nxt[v]++];
                if(!trav[i[1]]){
                        trav[i[1]]=1;
                        if(vis[i[0]]){
                                res.push_back(v);
                                cyc=i[0];
                                return;
                        }
                        dfs(i[0]);
                        res.push_back(v);
                        if(cyc==v){
                                for(const int&i:res){
                                        cout<<i<<' ';
                                        vis[i]=0;
                                }
                                res.clear();
                                cout<<'\n';
                                cyc=0;
                                vis[v]=1;
                        }
                        else if(cyc)return;
                }
        }
}

int main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
        int n,m;
        cin>>n>>m;
        for(int i=0,a,b;i<m;++i){
                cin>>a>>b;
                g[a].push_back({b,i});
                g[b].push_back({a,i});
        }
        for(int i=1;i<=n;++i)
                if(nxt[i]<g[i].size())dfs(i);
}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:13:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |         while(nxt[v]<g[v].size()){
      |               ~~~~~~^~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |                 if(nxt[i]<g[i].size())dfs(i);
      |                    ~~~~~~^~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 7 ms 12116 KB Output is correct
5 Correct 6 ms 12116 KB Output is correct
6 Correct 8 ms 12216 KB Output is correct
7 Correct 11 ms 12848 KB Output is correct
8 Correct 8 ms 12340 KB Output is correct
9 Correct 39 ms 15200 KB Output is correct
10 Correct 7 ms 12116 KB Output is correct
11 Correct 9 ms 12264 KB Output is correct
12 Correct 34 ms 15668 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 7 ms 11988 KB Output is correct
4 Correct 8 ms 12212 KB Output is correct
5 Correct 7 ms 12048 KB Output is correct
6 Correct 9 ms 12256 KB Output is correct
7 Correct 11 ms 12628 KB Output is correct
8 Correct 7 ms 12340 KB Output is correct
9 Correct 30 ms 15200 KB Output is correct
10 Correct 9 ms 12204 KB Output is correct
11 Correct 11 ms 12204 KB Output is correct
12 Correct 38 ms 15800 KB Output is correct
13 Correct 68 ms 28996 KB Output is correct
14 Correct 57 ms 17188 KB Output is correct
15 Correct 47 ms 16400 KB Output is correct
16 Correct 68 ms 28996 KB Output is correct
17 Correct 58 ms 16820 KB Output is correct
18 Correct 54 ms 20004 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12088 KB Output is correct
2 Correct 7 ms 11988 KB Output is correct
3 Correct 7 ms 12068 KB Output is correct
4 Correct 7 ms 12212 KB Output is correct
5 Correct 6 ms 12080 KB Output is correct
6 Correct 8 ms 12192 KB Output is correct
7 Correct 12 ms 12724 KB Output is correct
8 Correct 8 ms 12372 KB Output is correct
9 Correct 34 ms 15316 KB Output is correct
10 Correct 8 ms 12116 KB Output is correct
11 Correct 8 ms 12276 KB Output is correct
12 Correct 34 ms 15692 KB Output is correct
13 Correct 69 ms 28932 KB Output is correct
14 Correct 56 ms 17104 KB Output is correct
15 Correct 50 ms 16424 KB Output is correct
16 Correct 59 ms 28920 KB Output is correct
17 Correct 54 ms 16844 KB Output is correct
18 Correct 58 ms 20044 KB Output is correct
19 Correct 417 ms 97612 KB Output is correct
20 Correct 343 ms 38828 KB Output is correct
21 Correct 310 ms 34972 KB Output is correct
22 Correct 437 ms 97560 KB Output is correct
23 Correct 147 ms 27104 KB Output is correct
24 Correct 429 ms 37556 KB Output is correct
25 Correct 439 ms 52880 KB Output is correct