oj.uz

Submission #873769

# Submission time Handle Problem Language Result Execution time Memory
873769 2023-11-15T17:29:57 Z Victor Naboj (COCI22_naboj) C++17
40 / 110
 1000 ms 74044 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;
    rep(u,0,n) {
        trav(edge,graph[u]) value[u]+=edge.second;
        if(value[u]%sz(graph[u])==0) q.push(u);
    }

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

    while(!q.empty()) {
        ll u=q.front();
        q.pop();
        if(vis[u]) continue;

        vis[u]=1;
        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(sz(graph[v])==0||value[v]%sz(graph[v])==0) 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<<endl;
    }
    return 0;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 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 452 KB Output is correct
12 Correct 0 ms 344 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 498 ms 56264 KB Output is correct
2 Correct 532 ms 55996 KB Output is correct
3 Correct 266 ms 29708 KB Output is correct
4 Correct 516 ms 55996 KB Output is correct
5 Correct 499 ms 55796 KB Output is correct
6 Correct 513 ms 56776 KB Output is correct
7 Correct 503 ms 56520 KB Output is correct
8 Correct 384 ms 45808 KB Output is correct
9 Correct 519 ms 55844 KB Output is correct
10 Correct 539 ms 56396 KB Output is correct

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 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 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 460 KB Output is correct
8 Correct 0 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 452 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 498 ms 56264 KB Output is correct
16 Correct 532 ms 55996 KB Output is correct
17 Correct 266 ms 29708 KB Output is correct
18 Correct 516 ms 55996 KB Output is correct
19 Correct 499 ms 55796 KB Output is correct
20 Correct 513 ms 56776 KB Output is correct
21 Correct 503 ms 56520 KB Output is correct
22 Correct 384 ms 45808 KB Output is correct
23 Correct 519 ms 55844 KB Output is correct
24 Correct 539 ms 56396 KB Output is correct
25 Correct 490 ms 54108 KB Output is correct
26 Correct 437 ms 62804 KB Output is correct
27 Correct 472 ms 65356 KB Output is correct
28 Correct 540 ms 71632 KB Output is correct
29 Correct 349 ms 59124 KB Output is correct
30 Correct 641 ms 71104 KB Output is correct
31 Correct 32 ms 10064 KB Output is correct
32 Correct 608 ms 58660 KB Output is correct
33 Execution timed out 1027 ms 74044 KB Time limit exceeded
34 Halted 0 ms 0 KB -