oj.uz

답안 #293922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
293922 2020-09-08T13:46:22 Z 문홍윤(#5819) Acrobat (balkan16_acrobat) C++17
0 / 100
 187 ms 262148 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

struct UNION_FIND{
    int par[300010];
    void init(){for(int i=1; i<=300000; i++)par[i]=i;}
    int findpar(int num){
        if(num==par[num])return num;
        return par[num]=findpar(par[num]);
    }
    void mergepar(int a, int b){par[findpar(a)]=b;}
}uf;

int n, m, cnt[300010];
pii lin[300010];
vector<pii> link[300010];
vector<int> bip[300010];
vector<pair<int, pii> > ans;
bool ch[300010];

int dfs(int num, int par){
    ch[num]=true;
    int ret=cnt[num];
    for(auto i:link[num]){
        if(i.F==par)continue;
        if(dfs(i.F, num)){
            ans.eb(1, lin[i.S]);
            swap(lin[i.S].F, lin[i.S].S);
            ret++;
        }
    }
    return ret%2;
}

int main(){
    scanf("%d %d", &n, &m);
    uf.init();
    for(int i=1; i<=m; i++){
        scanf("%d %d", &lin[i].F, &lin[i].S);
        cnt[lin[i].F]++;
        if(uf.findpar(lin[i].F)!=uf.findpar(lin[i].S)){
            uf.mergepar(lin[i].F, lin[i].S);
            link[lin[i].F].eb(lin[i].S, i);
            link[lin[i].S].eb(lin[i].F, i);
        }
    }
    for(int i=1; i<=n; i++){
        if(ch[i])continue;
        if(dfs(i, 0))return !printf("-1");
    }
    for(int i=1; i<=m; i++)bip[lin[i].F].eb(lin[i].S);
    uf.init();
    memset(cnt, 0, sizeof cnt);
    for(int i=1; i<=n; i++){
        if(!bip[i].size())continue;
        for(int j=0; j<bip[i].size(); j+=2){
            uf.mergepar(bip[i][j], bip[i][j+1]);
        }
        for(auto j:bip[i])cnt[j]++;
    }
    for(int i=1; i<=n; i++){
        if(uf.findpar(1)!=uf.findpar(i)){
            uf.mergepar(1, i);
            ans.eb(2, mp(1, i));
            cnt[1]++;
            cnt[i]++;
        }
    }
    int nop=0;
    for(int i=1; i<=n; i++){
        if(cnt[i]%2==0)continue;
        if(nop){
            ans.eb(2, mp(nop, i));
            nop=0;
        }
        else nop=i;
    }
    printf("%d\n", ans.size());
    for(auto i:ans)printf("%d %d %d\n", i.F, i.S.F, i.S.S);
}

Compilation message

main.cpp: In function 'int main()':
main.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int j=0; j<bip[i].size(); j+=2){
      |                      ~^~~~~~~~~~~~~~
main.cpp:92:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wformat=]
   92 |     printf("%d\n", ans.size());
      |             ~^     ~~~~~~~~~~
      |              |             |
      |              int           std::vector<std::pair<int, std::pair<int, int> > >::size_type {aka long unsigned int}
      |             %ld
main.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   50 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d %d", &lin[i].F, &lin[i].S);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 187 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 176 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 180 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -