oj.uz

답안 #912880

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912880 2024-01-20T03:56:12 Z 1075508020060209tc 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 101020 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(long long int)':
postmen.cpp:18:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<long long 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: 'long long int' and 'std::vector<std::vector<long long 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: 'long long int' and 'std::vector<long long 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 6 ms 16888 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 5 ms 16824 KB Output is correct
4 Correct 7 ms 17336 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct
6 Correct 7 ms 17240 KB Output is correct
7 Correct 12 ms 18780 KB Output is correct
8 Correct 6 ms 17244 KB Output is correct
9 Correct 35 ms 28332 KB Output is correct
10 Correct 7 ms 16988 KB Output is correct
11 Correct 7 ms 17244 KB Output is correct
12 Correct 40 ms 28976 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 16732 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 7 ms 16884 KB Output is correct
4 Correct 7 ms 17244 KB Output is correct
5 Correct 6 ms 16984 KB Output is correct
6 Correct 6 ms 17244 KB Output is correct
7 Correct 9 ms 18804 KB Output is correct
8 Correct 6 ms 17244 KB Output is correct
9 Correct 33 ms 28544 KB Output is correct
10 Correct 7 ms 17212 KB Output is correct
11 Correct 8 ms 17240 KB Output is correct
12 Correct 38 ms 28976 KB Output is correct
13 Correct 64 ms 32916 KB Output is correct
14 Correct 73 ms 29376 KB Output is correct
15 Correct 59 ms 31660 KB Output is correct
16 Correct 56 ms 32972 KB Output is correct
17 Correct 56 ms 26440 KB Output is correct
18 Correct 50 ms 30660 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 16984 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 7 ms 16728 KB Output is correct
4 Correct 7 ms 17240 KB Output is correct
5 Correct 5 ms 16984 KB Output is correct
6 Correct 7 ms 17244 KB Output is correct
7 Correct 10 ms 18608 KB Output is correct
8 Correct 7 ms 17236 KB Output is correct
9 Correct 36 ms 28452 KB Output is correct
10 Correct 6 ms 16988 KB Output is correct
11 Correct 6 ms 17092 KB Output is correct
12 Correct 39 ms 28876 KB Output is correct
13 Correct 61 ms 32976 KB Output is correct
14 Correct 63 ms 29560 KB Output is correct
15 Correct 58 ms 31724 KB Output is correct
16 Correct 71 ms 33048 KB Output is correct
17 Correct 52 ms 26676 KB Output is correct
18 Correct 60 ms 30696 KB Output is correct
19 Execution timed out 684 ms 101020 KB Time limit exceeded
20 Halted 0 ms 0 KB -