oj.uz

Submission #912899

# Submission time Handle Problem Language Result Execution time Memory
912899 2024-01-20T04:18:55 Z 1075508020060209tc Senior Postmen (BOI14_postmen) C++14
55 / 100
 500 ms 73292 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;
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]^br[id]^nw;
    dfs(v);
}
ans[asz++]=nw;
}
vector<vector<int>>fans;
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);
}
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]);
            if(stk[ssz-1]==v){printf("\n");break;}
            visv[stk[ssz-1]]=0;
            //stk.pop();
            ssz--;
        }
//        fans.push_back(vc);
    }else{
        visv[v]=1;
        stk[ssz++]=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: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]++){
      |      ~~~~~~~^~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:63:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 | for(int i=0;i<fans.size();i++){
      |             ~^~~~~~~~~~~~
postmen.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int j=0;j<fans[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~
postmen.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d",&ar[i]);
      |     ~~~~~^~~~~~~~~~~~~
postmen.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d",&br[i]);
      |     ~~~~~^~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 5 ms 16884 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 6 ms 16988 KB Output is correct
5 Correct 5 ms 16732 KB Output is correct
6 Correct 6 ms 16988 KB Output is correct
7 Correct 8 ms 18012 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 41 ms 27080 KB Output is correct
10 Correct 7 ms 16988 KB Output is correct
11 Correct 6 ms 16988 KB Output is correct
12 Correct 43 ms 26960 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16732 KB Output is correct
2 Correct 5 ms 16728 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 7 ms 16988 KB Output is correct
5 Correct 5 ms 16728 KB Output is correct
6 Correct 7 ms 16984 KB Output is correct
7 Correct 10 ms 18012 KB Output is correct
8 Correct 6 ms 16988 KB Output is correct
9 Correct 35 ms 26820 KB Output is correct
10 Correct 5 ms 17152 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 41 ms 26960 KB Output is correct
13 Correct 71 ms 29832 KB Output is correct
14 Correct 65 ms 25680 KB Output is correct
15 Correct 83 ms 28628 KB Output is correct
16 Correct 55 ms 30044 KB Output is correct
17 Correct 90 ms 23120 KB Output is correct
18 Correct 53 ms 27248 KB Output is correct

Subtask #3
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 4 ms 16732 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 5 ms 16728 KB Output is correct
6 Correct 5 ms 16988 KB Output is correct
7 Correct 11 ms 18012 KB Output is correct
8 Correct 6 ms 16984 KB Output is correct
9 Correct 40 ms 26720 KB Output is correct
10 Correct 6 ms 16988 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 38 ms 27056 KB Output is correct
13 Correct 52 ms 29812 KB Output is correct
14 Correct 52 ms 25712 KB Output is correct
15 Correct 67 ms 28644 KB Output is correct
16 Correct 59 ms 29712 KB Output is correct
17 Correct 52 ms 23124 KB Output is correct
18 Correct 48 ms 27220 KB Output is correct
19 Execution timed out 635 ms 73292 KB Time limit exceeded
20 Halted 0 ms 0 KB -