oj.uz

답안 #912934

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
912934 2024-01-20T04:34:44 Z 1075508020060209tc 어르신 집배원 (BOI14_postmen) C++14
55 / 100
 500 ms 64572 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];
bitset<500005>vis;
bitset<500005>visv;

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;}else{
                cout<<' ';
            }

            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:22:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | for(;eit[nw]<e[nw].size();eit[nw]++){
      |      ~~~~~~~^~~~~~~~~~~~~

Subtask #1
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 5 ms 16732 KB Output is correct
3 Correct 5 ms 16732 KB Output is correct
4 Correct 6 ms 16988 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct
6 Correct 6 ms 16988 KB Output is correct
7 Correct 10 ms 17840 KB Output is correct
8 Correct 6 ms 16988 KB Output is correct
9 Correct 33 ms 23336 KB Output is correct
10 Correct 6 ms 16984 KB Output is correct
11 Correct 6 ms 17100 KB Output is correct
12 Correct 36 ms 23376 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 7 ms 16732 KB Output is correct
3 Correct 6 ms 16732 KB Output is correct
4 Correct 6 ms 16988 KB Output is correct
5 Correct 7 ms 17144 KB Output is correct
6 Correct 6 ms 16984 KB Output is correct
7 Correct 10 ms 17912 KB Output is correct
8 Correct 7 ms 16988 KB Output is correct
9 Correct 36 ms 23352 KB Output is correct
10 Correct 6 ms 16984 KB Output is correct
11 Correct 6 ms 16984 KB Output is correct
12 Correct 31 ms 23400 KB Output is correct
13 Correct 51 ms 26404 KB Output is correct
14 Correct 41 ms 22876 KB Output is correct
15 Correct 45 ms 24784 KB Output is correct
16 Correct 47 ms 26204 KB Output is correct
17 Correct 55 ms 20820 KB Output is correct
18 Correct 48 ms 23892 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 16728 KB Output is correct
2 Correct 5 ms 16728 KB Output is correct
3 Correct 6 ms 16740 KB Output is correct
4 Correct 6 ms 16988 KB Output is correct
5 Correct 6 ms 16988 KB Output is correct
6 Correct 7 ms 16988 KB Output is correct
7 Correct 11 ms 17756 KB Output is correct
8 Correct 6 ms 16988 KB Output is correct
9 Correct 31 ms 23280 KB Output is correct
10 Correct 6 ms 16988 KB Output is correct
11 Correct 6 ms 17100 KB Output is correct
12 Correct 30 ms 23380 KB Output is correct
13 Correct 90 ms 26196 KB Output is correct
14 Correct 42 ms 22876 KB Output is correct
15 Correct 40 ms 24940 KB Output is correct
16 Correct 82 ms 26292 KB Output is correct
17 Correct 52 ms 20668 KB Output is correct
18 Correct 59 ms 23888 KB Output is correct
19 Correct 454 ms 64484 KB Output is correct
20 Correct 439 ms 47960 KB Output is correct
21 Correct 338 ms 57700 KB Output is correct
22 Correct 391 ms 64572 KB Output is correct
23 Correct 122 ms 49732 KB Output is correct
24 Execution timed out 515 ms 36952 KB Time limit exceeded
25 Halted 0 ms 0 KB -