oj.uz

Submission #873770

# Submission time Handle Problem Language Result Execution time Memory
873770 2023-11-15T17:32:36 Z Victor Naboj (COCI22_naboj) C++17
110 / 110
 789 ms 77296 KB 
// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b) for (ll i = (a); i < (b); ++i)
#define per(i, a, b) for (ll i = (b) - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) (ll)x.size()
#define pb push_back
#define debug(x) cout<<#x<<" = "<<x<<endl

#define umap unordered_map
#define uset unordered_set

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> ppll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;

const ll INF = 1'000'000'007;

ll n,m;
vector<umap<ll,ll>> graph;
vector<ll> value;
vector<pll> order;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);

    cin>>n>>m;
    graph.resize(n);

    rep(i,0,m) {
        ll u,v;
        cin>>u>>v;
        --u; --v;
        graph[u].emplace(v,1);
        graph[v].emplace(u,0);
    }

    value.assign(n,0);

    queue<ll> q;
    vector<bool> vis;
    vis.assign(n,0);

    rep(u,0,n) {
        trav(edge,graph[u]) value[u]+=edge.second;
        if(value[u]%sz(graph[u])==0) {
            q.push(u);
            vis[u]=1;
        }
    }

    while(!q.empty()) {
        ll u=q.front();
        q.pop();

        if(sz(graph[u])) order.emplace_back(u,value[u]/sz(graph[u]));
        else order.emplace_back(u,0);

        trav(edge,graph[u]) {
            ll v,w;
            tie(v,w)=edge;
            graph[v].erase({u});
            value[v]-=1-w;


            if(!vis[v]&&(sz(graph[v])==0||value[v]%sz(graph[v])==0)) {
                vis[v]=1;
                q.push(v);
            }
        }
    }

    if(sz(order)!=n) cout<<-1<<endl;
    else {
        cout<<n<<endl;
        reverse(all(order));
        trav(item,order) cout<<item.first+1<<' '<<item.second<<'\n';
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 53504 KB Output is correct
2 Correct 271 ms 54556 KB Output is correct
3 Correct 115 ms 28352 KB Output is correct
4 Correct 301 ms 54980 KB Output is correct
5 Correct 282 ms 53288 KB Output is correct
6 Correct 274 ms 53440 KB Output is correct
7 Correct 268 ms 54440 KB Output is correct
8 Correct 199 ms 43468 KB Output is correct
9 Correct 272 ms 53880 KB Output is correct
10 Correct 272 ms 53440 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 297 ms 53504 KB Output is correct
16 Correct 271 ms 54556 KB Output is correct
17 Correct 115 ms 28352 KB Output is correct
18 Correct 301 ms 54980 KB Output is correct
19 Correct 282 ms 53288 KB Output is correct
20 Correct 274 ms 53440 KB Output is correct
21 Correct 268 ms 54440 KB Output is correct
22 Correct 199 ms 43468 KB Output is correct
23 Correct 272 ms 53880 KB Output is correct
24 Correct 272 ms 53440 KB Output is correct
25 Correct 412 ms 49172 KB Output is correct
26 Correct 409 ms 59844 KB Output is correct
27 Correct 431 ms 60572 KB Output is correct
28 Correct 521 ms 65900 KB Output is correct
29 Correct 328 ms 57288 KB Output is correct
30 Correct 490 ms 65208 KB Output is correct
31 Correct 31 ms 9040 KB Output is correct
32 Correct 332 ms 55236 KB Output is correct
33 Correct 679 ms 68324 KB Output is correct
34 Correct 416 ms 60068 KB Output is correct
35 Correct 743 ms 74636 KB Output is correct
36 Correct 323 ms 57272 KB Output is correct
37 Correct 617 ms 70848 KB Output is correct
38 Correct 495 ms 66740 KB Output is correct
39 Correct 678 ms 74972 KB Output is correct
40 Correct 572 ms 69320 KB Output is correct
41 Correct 592 ms 68160 KB Output is correct
42 Correct 789 ms 77296 KB Output is correct
43 Correct 387 ms 60644 KB Output is correct
44 Correct 756 ms 77156 KB Output is correct
45 Correct 348 ms 59316 KB Output is correct
46 Correct 579 ms 69396 KB Output is correct