oj.uz

Submission #912913

# Submission time Handle Problem Language Result Execution time Memory
912913 2024-01-20T04:26:54 Z 1075508020060209tc Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 65480 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];

int ans[500005];
int asz;
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]^nw;
    dfs(v);
}
ans[asz++]=nw;
}

int stk[510005];
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];
 //   scanf("%d",&ar[i]);
   // scanf("%d",&br[i]);
    e[ar[i]].push_back(i);
    e[br[i]].push_back(i);
    ar[i]^=br[i];
}
dfs(1);
int ssz=0;
//stack<int>stk;
for(int i=0;i<asz;i++){
    //vector<int>vc;
    int v=ans[i];
    if(visv[v]){
        while(1){
  //          vc.push_back(stk.back());
            //printf("%d ",stk[ssz-1]);
            cout<<stk[ssz-1]<<" ";
            if(stk[ssz-1]==v){cout<<"\n";break;}

            visv[stk[ssz-1]]=0;
            //stk.pop();
            ssz--;
        }
//        fans.push_back(vc);
    }else{
        visv[v]=1;
        stk[ssz++]=v;
    }
}return 0;

}

Compilation message

postmen.cpp: In function 'void dfs(int)':
postmen.cpp:20:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | for(;eit[nw]<e[nw].size();eit[nw]++){
      |      ~~~~~~~^~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14680 KB Output is correct
2 Correct 5 ms 14684 KB Output is correct
3 Correct 5 ms 14680 KB Output is correct
4 Correct 6 ms 14940 KB Output is correct
5 Correct 5 ms 14936 KB Output is correct
6 Correct 7 ms 14940 KB Output is correct
7 Correct 9 ms 15708 KB Output is correct
8 Correct 7 ms 15092 KB Output is correct
9 Correct 33 ms 23548 KB Output is correct
10 Correct 6 ms 14936 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 37 ms 23556 KB Output is correct

Subtask #2
17.0 / 17.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 5 ms 14684 KB Output is correct
4 Correct 6 ms 14936 KB Output is correct
5 Correct 5 ms 14684 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 8 ms 15704 KB Output is correct
8 Correct 6 ms 14936 KB Output is correct
9 Correct 33 ms 23384 KB Output is correct
10 Correct 5 ms 14936 KB Output is correct
11 Correct 6 ms 14936 KB Output is correct
12 Correct 37 ms 23712 KB Output is correct
13 Correct 51 ms 26652 KB Output is correct
14 Correct 39 ms 23256 KB Output is correct
15 Correct 48 ms 25276 KB Output is correct
16 Correct 47 ms 26636 KB Output is correct
17 Correct 41 ms 21100 KB Output is correct
18 Correct 92 ms 24140 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 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 5 ms 14940 KB Output is correct
5 Correct 6 ms 14936 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 11 ms 15708 KB Output is correct
8 Correct 6 ms 14940 KB Output is correct
9 Correct 34 ms 23436 KB Output is correct
10 Correct 5 ms 14940 KB Output is correct
11 Correct 5 ms 14940 KB Output is correct
12 Correct 43 ms 23640 KB Output is correct
13 Correct 55 ms 26676 KB Output is correct
14 Correct 53 ms 23204 KB Output is correct
15 Correct 55 ms 25292 KB Output is correct
16 Correct 41 ms 26456 KB Output is correct
17 Correct 48 ms 21072 KB Output is correct
18 Correct 42 ms 24152 KB Output is correct
19 Correct 498 ms 65468 KB Output is correct
20 Correct 403 ms 48700 KB Output is correct
21 Correct 446 ms 58632 KB Output is correct
22 Execution timed out 582 ms 65480 KB Time limit exceeded
23 Halted 0 ms 0 KB -