oj.uz

Submission #912886

# Submission time Handle Problem Language Result Execution time Memory
912886 2024-01-20T04:00:08 Z 1075508020060209tc Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 73296 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define X first
#define Y second
#define SZ(x) (int)(x).size()

int n;int m;
int ar[500005];
int br[500005];
vector<int>e[500005];
int eit[500005];
bool vis[500005];
bool visv[500005];
vector<int>ans;
void dfs(int nw){
for(;eit[nw]<e[nw].size();eit[nw]++){
    int id=e[nw][eit[nw]];
    if(vis[id]){continue;}
    vis[id]=1;
    int v=ar[id]^br[id]^nw;
    dfs(v);
}
ans.push_back(nw);
}
vector<vector<int>>fans;

signed main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
    cin>>ar[i]>>br[i];
    e[ar[i]].push_back(i);
    e[br[i]].push_back(i);
}
dfs(1);
vector<int>stk;
for(int i=0;i<ans.size();i++){
    //vector<int>vc;
    int v=ans[i];
    if(visv[v]){
        while(1){
  //          vc.push_back(stk.back());
            cout<<stk.back()<<" ";
            if(stk.back()==v){cout<<"\n";break;}
            visv[stk.back()]=0;
            stk.pop_back();
        }
//        fans.push_back(vc);
    }else{
        visv[v]=1;
        stk.push_back(v);
    }
}return 0;
for(int i=0;i<fans.size();i++){
    for(int j=0;j<fans[i].size();j++){
        cout<<fans[i][j]<<" ";
    }cout<<"\n";
}


}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:18:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | for(;eit[nw]<e[nw].size();eit[nw]++){
      |      ~~~~~~~^~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:40:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 | for(int i=0;i<ans.size();i++){
      |             ~^~~~~~~~~~~
postmen.cpp:57:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 | for(int i=0;i<fans.size();i++){
      |             ~^~~~~~~~~~~~
postmen.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int j=0;j<fans[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14680 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 7 ms 15096 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 6 ms 15196 KB Output is correct
7 Correct 10 ms 16216 KB Output is correct
8 Correct 7 ms 14936 KB Output is correct
9 Correct 40 ms 23244 KB Output is correct
10 Correct 6 ms 15096 KB Output is correct
11 Correct 8 ms 14940 KB Output is correct
12 Correct 43 ms 23584 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 6 ms 14836 KB Output is correct
3 Correct 5 ms 14680 KB Output is correct
4 Correct 8 ms 14936 KB Output is correct
5 Correct 5 ms 14936 KB Output is correct
6 Correct 5 ms 15196 KB Output is correct
7 Correct 9 ms 16216 KB Output is correct
8 Correct 6 ms 15044 KB Output is correct
9 Correct 28 ms 23248 KB Output is correct
10 Correct 8 ms 14936 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 40 ms 23652 KB Output is correct
13 Correct 46 ms 26700 KB Output is correct
14 Correct 62 ms 22380 KB Output is correct
15 Correct 39 ms 25032 KB Output is correct
16 Correct 100 ms 26588 KB Output is correct
17 Correct 43 ms 19656 KB Output is correct
18 Correct 57 ms 23792 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 14684 KB Output is correct
2 Correct 5 ms 14680 KB Output is correct
3 Correct 5 ms 14780 KB Output is correct
4 Correct 5 ms 14940 KB Output is correct
5 Correct 5 ms 14940 KB Output is correct
6 Correct 7 ms 15348 KB Output is correct
7 Correct 10 ms 16112 KB Output is correct
8 Correct 5 ms 14940 KB Output is correct
9 Correct 30 ms 23240 KB Output is correct
10 Correct 7 ms 14936 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 40 ms 23496 KB Output is correct
13 Correct 81 ms 26688 KB Output is correct
14 Correct 57 ms 22472 KB Output is correct
15 Correct 57 ms 25092 KB Output is correct
16 Correct 61 ms 26700 KB Output is correct
17 Correct 51 ms 19660 KB Output is correct
18 Correct 89 ms 23756 KB Output is correct
19 Execution timed out 533 ms 73296 KB Time limit exceeded
20 Halted 0 ms 0 KB -