oj.uz

Submission #261227

# Submission time Handle Problem Language Result Execution time Memory
261227 2020-08-11T14:58:33 Z eohomegrownapps Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 139256 KB 
#include <bits/stdc++.h>
using namespace std;

int tarr[1000000];
int ptr = 0;
bool visited[1000000];
unordered_set<int> adjlist[1000000];

inline void deleteEdge(int a, int b){
    adjlist[a].erase(b);
    adjlist[b].erase(a);
}
void tour(int node){
    while (adjlist[node].size()>0){
        int newnode = *adjlist[node].begin();
        deleteEdge(node, newnode);
        tour(newnode);
    }
    int i = node;
    if (visited[i]){
        cout<<i+1<<' ';
        while (ptr>0&&tarr[ptr-1]!=i){
            cout<<tarr[ptr-1]+1<<' ';
            visited[tarr[ptr-1]]=false;
            ptr--;
        }
        cout<<'\n';
    } else {
        visited[i]=true;
        ptr++;
        tarr[ptr-1]=i;
    }
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n,m;
    cin>>n>>m;
    for (int i = 0; i<n; i++){
        visited[i]=0;
    }
    //adjlist.resize(n);
    for (int i = 0; i<m; i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        adjlist[a].insert(b);
        adjlist[b].insert(a);
    }
    tour(0);
}

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 55160 KB Output is correct
2 Correct 44 ms 55160 KB Output is correct
3 Correct 44 ms 55160 KB Output is correct
4 Correct 46 ms 55672 KB Output is correct
5 Correct 45 ms 55288 KB Output is correct
6 Correct 53 ms 55808 KB Output is correct
7 Correct 64 ms 57336 KB Output is correct
8 Correct 46 ms 55416 KB Output is correct
9 Correct 183 ms 70476 KB Output is correct
10 Correct 47 ms 55416 KB Output is correct
11 Correct 47 ms 55552 KB Output is correct
12 Correct 199 ms 70740 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 55160 KB Output is correct
2 Correct 44 ms 55168 KB Output is correct
3 Correct 44 ms 55296 KB Output is correct
4 Correct 47 ms 55672 KB Output is correct
5 Correct 45 ms 55288 KB Output is correct
6 Correct 48 ms 55800 KB Output is correct
7 Correct 56 ms 57336 KB Output is correct
8 Correct 45 ms 55424 KB Output is correct
9 Correct 190 ms 70500 KB Output is correct
10 Correct 49 ms 55544 KB Output is correct
11 Correct 46 ms 55544 KB Output is correct
12 Correct 197 ms 71032 KB Output is correct
13 Correct 199 ms 71928 KB Output is correct
14 Correct 210 ms 68624 KB Output is correct
15 Correct 193 ms 71176 KB Output is correct
16 Correct 173 ms 71928 KB Output is correct
17 Correct 213 ms 65804 KB Output is correct
18 Correct 185 ms 70776 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 55168 KB Output is correct
2 Correct 44 ms 55160 KB Output is correct
3 Correct 45 ms 55160 KB Output is correct
4 Correct 47 ms 55672 KB Output is correct
5 Correct 44 ms 55288 KB Output is correct
6 Correct 48 ms 55928 KB Output is correct
7 Correct 58 ms 57336 KB Output is correct
8 Correct 46 ms 55544 KB Output is correct
9 Correct 159 ms 70520 KB Output is correct
10 Correct 47 ms 55416 KB Output is correct
11 Correct 48 ms 55544 KB Output is correct
12 Correct 176 ms 70776 KB Output is correct
13 Correct 176 ms 71928 KB Output is correct
14 Correct 175 ms 68600 KB Output is correct
15 Correct 181 ms 71176 KB Output is correct
16 Correct 183 ms 72056 KB Output is correct
17 Correct 210 ms 65784 KB Output is correct
18 Correct 200 ms 70776 KB Output is correct
19 Execution timed out 815 ms 139256 KB Time limit exceeded
20 Halted 0 ms 0 KB -