oj.uz

답안 #912898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912898 2024-01-20T04:16:34 Z 1075508020060209tc 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 73588 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];
    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());
            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;
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:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 | for(int i=0;i<fans.size();i++){
      |             ~^~~~~~~~~~~~
postmen.cpp:62:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int j=0;j<fans[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 4 ms 16992 KB Output is correct
4 Correct 5 ms 16984 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 6 ms 17244 KB Output is correct
7 Correct 9 ms 18020 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 31 ms 26840 KB Output is correct
10 Correct 5 ms 16988 KB Output is correct
11 Correct 7 ms 16988 KB Output is correct
12 Correct 38 ms 26964 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16728 KB Output is correct
2 Correct 4 ms 16844 KB Output is correct
3 Correct 4 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 6 ms 17396 KB Output is correct
7 Correct 9 ms 18012 KB Output is correct
8 Correct 6 ms 16984 KB Output is correct
9 Correct 35 ms 26972 KB Output is correct
10 Correct 6 ms 16984 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 34 ms 26968 KB Output is correct
13 Correct 74 ms 29780 KB Output is correct
14 Correct 50 ms 25856 KB Output is correct
15 Correct 42 ms 28616 KB Output is correct
16 Correct 89 ms 29644 KB Output is correct
17 Correct 43 ms 23176 KB Output is correct
18 Correct 43 ms 27220 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 4 ms 16732 KB Output is correct
3 Correct 5 ms 16732 KB Output is correct
4 Correct 5 ms 16988 KB Output is correct
5 Correct 5 ms 16984 KB Output is correct
6 Correct 6 ms 17244 KB Output is correct
7 Correct 9 ms 18012 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 30 ms 26708 KB Output is correct
10 Correct 5 ms 16984 KB Output is correct
11 Correct 5 ms 17036 KB Output is correct
12 Correct 33 ms 27028 KB Output is correct
13 Correct 77 ms 29628 KB Output is correct
14 Correct 48 ms 25828 KB Output is correct
15 Correct 41 ms 28624 KB Output is correct
16 Correct 75 ms 29780 KB Output is correct
17 Correct 41 ms 23024 KB Output is correct
18 Correct 42 ms 27332 KB Output is correct
19 Execution timed out 522 ms 73588 KB Time limit exceeded
20 Halted 0 ms 0 KB -