oj.uz

Submission #94665

# Submission time Handle Problem Language Result Execution time Memory
94665 2019-01-22T11:16:51 Z Alexa2001 Praktični (COCI18_prakticni) C++17
130 / 130
 209 ms 16468 KB 
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;

int xr[Nmax], Cost[Nmax], up[Nmax];
vector<int> v[Nmax];
vector< pair<int,int> > E;
int used[Nmax];


void dfs(int node, int dad = 0)
{
    used[node] = 1;

    for(auto it : v[node])
    {
        int son, cost;
        son = node ^ xr[it], cost = Cost[it];

        if(son != dad)
        {
            if(!used[son])
            {
                up[son] = up[node] ^ cost;
                dfs(son, node);
            }
            else if(used[son] == 1)
            {
                cost ^= up[node] ^ up[son];
                if(cost) E.push_back({cost, it});
            }
        }
    }

    used[node] = 2;
}

int main()
{
 //  freopen("input", "r", stdin);

    int n, m, x, y, z, i;

    cin >> n >> m;
    for(i=1; i<=m; ++i)
    {
        cin >> x >> y >> z;
        xr[i] = x^y, Cost[i] = z;
        v[x].push_back(i);
        v[y].push_back(i);
    }

    dfs(1);

    vector< vector<int> > answer;

    for(i=0; i<30; ++i)
    {
        int val = 0;
        for(auto it : E)
            if(it.first & (1<<i)) val = it.first;

        if(!val) continue;

        answer.push_back(vector<int> () );
        answer.back().push_back(val);

        vector<int> ids;

        for(auto &it : E)
            if(it.first & (1<<i)) ids.push_back(it.second), it.first ^= val;

        answer.back().push_back(ids.size());
        for(auto it : ids) answer.back().push_back(it);
    }

    cout << answer.size() << '\n';
    for(auto it : answer)
    {
        for(auto x : it) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 6648 KB Output is correct
2 Correct 70 ms 7032 KB Output is correct
3 Correct 16 ms 3576 KB Output is correct
4 Correct 16 ms 3704 KB Output is correct
5 Correct 150 ms 12024 KB Output is correct
6 Correct 161 ms 11100 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4348 KB Output is correct
2 Correct 31 ms 4472 KB Output is correct
3 Correct 44 ms 5240 KB Output is correct
4 Correct 49 ms 5624 KB Output is correct
5 Correct 122 ms 10104 KB Output is correct
6 Correct 76 ms 7288 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 7544 KB Output is correct
2 Correct 130 ms 9384 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 10172 KB Output is correct
2 Correct 181 ms 14192 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 8496 KB Output is correct
2 Correct 131 ms 9336 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 10856 KB Output is correct
2 Correct 84 ms 7032 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 10824 KB Output is correct
2 Correct 129 ms 12400 KB Output is correct
3 Correct 129 ms 9480 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 14196 KB Output is correct
2 Correct 209 ms 16468 KB Output is correct
3 Correct 209 ms 15344 KB Output is correct

Subtask #9
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 5244 KB Output is correct
2 Correct 60 ms 6136 KB Output is correct
3 Correct 162 ms 11356 KB Output is correct

Subtask #10
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 11640 KB Output is correct
2 Correct 101 ms 7968 KB Output is correct
3 Correct 186 ms 14504 KB Output is correct