oj.uz

Submission #912920

# Submission time Handle Problem Language Result Execution time Memory
912920 2024-01-20T04:28:17 Z 1075508020060209tc Senior Postmen (BOI14_postmen) C++11
55 / 100
 500 ms 65460 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 5 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 5 ms 14936 KB Output is correct
5 Correct 6 ms 14684 KB Output is correct
6 Correct 5 ms 14936 KB Output is correct
7 Correct 9 ms 16052 KB Output is correct
8 Correct 6 ms 14940 KB Output is correct
9 Correct 27 ms 23384 KB Output is correct
10 Correct 7 ms 14936 KB Output is correct
11 Correct 8 ms 14936 KB Output is correct
12 Correct 29 ms 23644 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 5 ms 14680 KB Output is correct
3 Correct 4 ms 14684 KB Output is correct
4 Correct 7 ms 15096 KB Output is correct
5 Correct 4 ms 14940 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 12 ms 15964 KB Output is correct
8 Correct 5 ms 14936 KB Output is correct
9 Correct 29 ms 23476 KB Output is correct
10 Correct 7 ms 14936 KB Output is correct
11 Correct 6 ms 15096 KB Output is correct
12 Correct 29 ms 23644 KB Output is correct
13 Correct 53 ms 26704 KB Output is correct
14 Correct 58 ms 23116 KB Output is correct
15 Correct 46 ms 25224 KB Output is correct
16 Correct 64 ms 26444 KB Output is correct
17 Correct 53 ms 21180 KB Output is correct
18 Correct 57 ms 24260 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 6 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 14940 KB Output is correct
6 Correct 6 ms 14940 KB Output is correct
7 Correct 8 ms 15708 KB Output is correct
8 Correct 6 ms 15044 KB Output is correct
9 Correct 30 ms 23380 KB Output is correct
10 Correct 6 ms 14936 KB Output is correct
11 Correct 6 ms 14940 KB Output is correct
12 Correct 30 ms 23636 KB Output is correct
13 Correct 62 ms 26464 KB Output is correct
14 Correct 38 ms 23120 KB Output is correct
15 Correct 39 ms 25204 KB Output is correct
16 Correct 49 ms 26624 KB Output is correct
17 Correct 44 ms 21116 KB Output is correct
18 Correct 48 ms 24280 KB Output is correct
19 Correct 492 ms 65396 KB Output is correct
20 Correct 467 ms 48864 KB Output is correct
21 Correct 466 ms 58560 KB Output is correct
22 Execution timed out 533 ms 65460 KB Time limit exceeded
23 Halted 0 ms 0 KB -