oj.uz

Submission #912936

# Submission time Handle Problem Language Result Execution time Memory
912936 2024-01-20T04:35:30 Z 1075508020060209tc Senior Postmen (BOI14_postmen) C++17
55 / 100
 500 ms 64508 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];
bitset<500005>vis;
bitset<500005>visv;

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;}else{
                cout<<' ';
            }

            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:22:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | for(;eit[nw]<e[nw].size();eit[nw]++){
      |      ~~~~~~~^~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 6 ms 16732 KB Output is correct
4 Correct 6 ms 16988 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 7 ms 16984 KB Output is correct
7 Correct 10 ms 17756 KB Output is correct
8 Correct 6 ms 16988 KB Output is correct
9 Correct 35 ms 23120 KB Output is correct
10 Correct 6 ms 16988 KB Output is correct
11 Correct 7 ms 16988 KB Output is correct
12 Correct 32 ms 23380 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 6 ms 16732 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 7 ms 16984 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct
6 Correct 6 ms 16988 KB Output is correct
7 Correct 10 ms 17756 KB Output is correct
8 Correct 6 ms 16992 KB Output is correct
9 Correct 33 ms 23128 KB Output is correct
10 Correct 7 ms 16984 KB Output is correct
11 Correct 6 ms 17236 KB Output is correct
12 Correct 32 ms 23384 KB Output is correct
13 Correct 59 ms 26192 KB Output is correct
14 Correct 49 ms 22864 KB Output is correct
15 Correct 42 ms 25028 KB Output is correct
16 Correct 76 ms 26192 KB Output is correct
17 Correct 56 ms 21024 KB Output is correct
18 Correct 75 ms 23804 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16884 KB Output is correct
2 Correct 5 ms 16728 KB Output is correct
3 Correct 6 ms 16732 KB Output is correct
4 Correct 7 ms 16988 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct
6 Correct 7 ms 16988 KB Output is correct
7 Correct 9 ms 17752 KB Output is correct
8 Correct 6 ms 16984 KB Output is correct
9 Correct 26 ms 23132 KB Output is correct
10 Correct 6 ms 16988 KB Output is correct
11 Correct 7 ms 16984 KB Output is correct
12 Correct 29 ms 23524 KB Output is correct
13 Correct 47 ms 26260 KB Output is correct
14 Correct 40 ms 22872 KB Output is correct
15 Correct 38 ms 24776 KB Output is correct
16 Correct 53 ms 26268 KB Output is correct
17 Correct 48 ms 20816 KB Output is correct
18 Correct 58 ms 23908 KB Output is correct
19 Execution timed out 525 ms 64508 KB Time limit exceeded
20 Halted 0 ms 0 KB -