oj.uz

Submission #293848

# Submission time Handle Problem Language Result Execution time Memory
293848 2020-09-08T13:02:34 Z 반딧불(#5811) None (balkan16_acrobat) C++17
0 / 100
 80 ms 62492 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void massert(bool cond){
    if(!cond){
        printf("-1");
        exit(0);
    }
}

struct Answer{
    int a, b, c;
    Answer(){}
    Answer(int a, int b, int c): a(a), b(b), c(c){}
};
vector<Answer> ans;

int n, m;
int edgeX[300002], edgeY[300002];
vector<int> linkDual[300002];
int degA[300002], degB[300002];

bool visited[300002];
int group[300002], groupNum, groupRoot[300002];
int DP[300002];
vector<int> spanningChild[300002];

unordered_set<int> edgeSet[300002];

void dfs(int x){
    visited[x] = 1, group[x] = groupNum;
    for(auto y: linkDual[x]){
        if(visited[y]) continue;
        dfs(y);
        spanningChild[x].push_back(y);
    }
}
void dfs2(int x){
    for(auto y: spanningChild[x]){
        dfs2(y);
        DP[x] += DP[y];

        if(DP[y]%2==1){
            if(edgeSet[x].find(y) != edgeSet[x].end()) ans.push_back({1, x, y}), degA[x]--, degB[x]++, degA[y]++, degB[y]--;
            else ans.push_back({1, y, x}), degA[y]--, degB[y]++, degA[x]++, degB[x]--;
        }
    }
}

int realDegA[300002], realDegB[300002];

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        int x, y;
        scanf("%d %d", &x, &y);
        edgeX[i] = x, edgeY[i] = y;
        linkDual[x].push_back(y), linkDual[y].push_back(x);
        edgeSet[x].insert(y);
        degA[x]++, degB[y]++;
        realDegA[x]++, realDegB[y]++;
    }

    for(int i=1; i<=n; i++){
        if(!visited[i]){
            groupRoot[++groupNum] = i;
            dfs(i);
        }
    }

    vector<pair<int, int> > degAVec;
    for(int i=1; i<=n; i++){
        if(degA[i]%2 == 1) degAVec.push_back({group[i], i});
    }
    sort(degAVec.begin(), degAVec.end());

    massert(degAVec.size() % 2 == 0);
    for(int i=0; i<(int)degAVec.size(); i+=2){
        massert(group[degAVec[i].first] == group[degAVec[i+1].first]);
        DP[degAVec[i].second]++, DP[degAVec[i+1].second]++;
    }

    for(int i=1; i<=groupNum; i++){
        dfs2(groupRoot[i]);
    }

    vector<int> oddB;
    for(int i=1; i<=n; i++) if(degB[i]%2) oddB.push_back(i);
    massert(oddB.size() % 2 == 0);
    sort(oddB.begin(), oddB.end());

    if(oddB.size() == 2 && oddB.back() - oddB.front() == 1){
        for(int i=1; i<n; i++) if(i != oddB.front()) ans.push_back({2, i, i+1});
        ans.push_back({2, n, 1});
    }
    else{
        int ts = (int)oddB.size() / 2;
        for(int i=0; i<ts; i++) ans.push_back({2, oddB[i], oddB[i+ts]});
        for(int i=1; i<n; i++) ans.push_back({2, i, i+1});
        ans.push_back({2, n, 1});
    }

    printf("%d\n", (int)ans.size());
    for(int i=0; i<(int)ans.size(); i++){
        if(ans[i].a == 1) realDegA[ans[i].b]--, realDegB[ans[i].b]++, realDegA[ans[i].c]++, realDegB[ans[i].c]--;
        else realDegB[ans[i].b]++, realDegB[ans[i].c]++;
        printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
    }

    for(int i=1; i<=n; i++) assert(realDegA[i]%2==0 && realDegB[i]%2==0);
}

Compilation message

main.cpp: In function 'int main()':
main.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 30840 KB Output is correct
2 Correct 22 ms 30892 KB Output is correct
3 Correct 27 ms 30848 KB Output is correct
4 Correct 24 ms 30976 KB Output is correct
5 Correct 24 ms 30960 KB Output is correct
6 Correct 23 ms 30976 KB Output is correct
7 Correct 24 ms 30900 KB Output is correct
8 Correct 23 ms 30976 KB Output is correct
9 Runtime error 68 ms 62492 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 30848 KB Output is correct
2 Correct 23 ms 30964 KB Output is correct
3 Correct 22 ms 30952 KB Output is correct
4 Correct 23 ms 30848 KB Output is correct
5 Correct 23 ms 30972 KB Output is correct
6 Correct 22 ms 30968 KB Output is correct
7 Correct 23 ms 30976 KB Output is correct
8 Correct 27 ms 30976 KB Output is correct
9 Runtime error 80 ms 62456 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 30848 KB Output is correct
2 Correct 28 ms 30848 KB Output is correct
3 Correct 22 ms 30848 KB Output is correct
4 Correct 29 ms 30976 KB Output is correct
5 Correct 24 ms 30936 KB Output is correct
6 Correct 27 ms 30976 KB Output is correct
7 Correct 33 ms 30976 KB Output is correct
8 Correct 22 ms 30976 KB Output is correct
9 Runtime error 79 ms 62472 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -