oj.uz

답안 #912881

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912881 2024-01-20T03:56:47 Z 1075508020060209tc 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 78296 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];
int vis[500005];
int visv[500005];
vector<int>ans;
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.push_back(nw);
}
vector<vector<int>>fans;

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);
vector<int>stk;
for(int i=0;i<ans.size();i++){
    vector<int>vc;
    int v=ans[i];
    if(visv[v]){
        while(1){
            vc.push_back(stk.back());
            if(stk.back()==v){break;}
            visv[stk.back()]=0;
            stk.pop_back();
        }
        fans.push_back(vc);
    }else{
        visv[v]=1;
        stk.push_back(v);
    }
}
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:18:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | for(;eit[nw]<e[nw].size();eit[nw]++){
      |      ~~~~~~~^~~~~~~~~~~~~
postmen.cpp: In function 'int main()':
postmen.cpp:40:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 | for(int i=0;i<ans.size();i++){
      |             ~^~~~~~~~~~~
postmen.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 | for(int i=0;i<fans.size();i++){
      |             ~^~~~~~~~~~~~
postmen.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int j=0;j<fans[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 5 ms 16728 KB Output is correct
4 Correct 6 ms 17244 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 6 ms 17240 KB Output is correct
7 Correct 9 ms 18268 KB Output is correct
8 Correct 6 ms 16984 KB Output is correct
9 Correct 31 ms 25824 KB Output is correct
10 Correct 6 ms 16988 KB Output is correct
11 Correct 6 ms 16988 KB Output is correct
12 Correct 32 ms 26044 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16728 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 6 ms 16984 KB Output is correct
4 Correct 8 ms 17244 KB Output is correct
5 Correct 7 ms 16984 KB Output is correct
6 Correct 6 ms 17244 KB Output is correct
7 Correct 9 ms 18268 KB Output is correct
8 Correct 5 ms 16988 KB Output is correct
9 Correct 31 ms 25800 KB Output is correct
10 Correct 7 ms 16984 KB Output is correct
11 Correct 6 ms 16988 KB Output is correct
12 Correct 40 ms 26016 KB Output is correct
13 Correct 52 ms 29212 KB Output is correct
14 Correct 55 ms 25852 KB Output is correct
15 Correct 44 ms 29388 KB Output is correct
16 Correct 65 ms 29244 KB Output is correct
17 Correct 53 ms 23772 KB Output is correct
18 Correct 46 ms 27460 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 6 ms 16728 KB Output is correct
4 Correct 6 ms 17244 KB Output is correct
5 Correct 5 ms 16988 KB Output is correct
6 Correct 6 ms 17244 KB Output is correct
7 Correct 9 ms 18268 KB Output is correct
8 Correct 6 ms 16988 KB Output is correct
9 Correct 35 ms 25804 KB Output is correct
10 Correct 6 ms 16984 KB Output is correct
11 Correct 5 ms 16988 KB Output is correct
12 Correct 33 ms 26056 KB Output is correct
13 Correct 55 ms 29228 KB Output is correct
14 Correct 59 ms 25672 KB Output is correct
15 Correct 43 ms 29380 KB Output is correct
16 Correct 71 ms 29084 KB Output is correct
17 Correct 52 ms 23644 KB Output is correct
18 Correct 45 ms 27472 KB Output is correct
19 Execution timed out 518 ms 78296 KB Time limit exceeded
20 Halted 0 ms 0 KB -