oj.uz

Submission #57744

# Submission time Handle Problem Language Result Execution time Memory
57744 2018-07-16T01:27:59 Z Benq KOVANICE (COI15_kovanice) C++14
100 / 100
 607 ms 63652 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 300001;


struct Topo {
    int N, in[MX], A[MX], B[MX];
    vi res, adj[MX], radj[MX];
    
    void addEdge(int x, int y) {
    	adj[x].pb(y), in[y] ++;
    	radj[y].pb(x);
    }
    
    void sort() {
        queue<int> todo;
        FOR(i,1,MX) if (in[i] == 0) todo.push(i);
        while (sz(todo)) {
            int x = todo.front(); todo.pop();
            res.pb(x);
            for (int i: adj[x]) {
                in[i] --;
                if (!in[i]) todo.push(i);
            }
        }
    }
    
    void gen() {
    	F0Rd(i,sz(res)) {
    		for (int j: adj[res[i]]) A[res[i]] = max(A[res[i]],A[j]);
    		A[res[i]] ++;
    	}
    	F0R(i,sz(res)) {
    		for (int j: radj[res[i]]) B[res[i]] = max(B[res[i]],B[j]);
    		B[res[i]] ++;
    	}
    }
};

Topo T;

template<int SZ> struct DSU {
    int par[SZ], sz[SZ];
    DSU() {
        F0R(i,SZ) par[i] = i, sz[i] = 1;
    }
    
    int get(int x) { // path compression
    	if (par[x] != x) par[x] = get(par[x]);
    	return par[x];
    }
    
    bool unite(int x, int y) { // union-by-rank
    	x = get(x), y = get(y);
    	if (x == y) return 0;
    	if (sz[x] < sz[y]) swap(x,y);
    	sz[x] += sz[y], par[y] = x;
    	return 1;
    }
};

DSU<MX> D;

int N,M,V;

bool isDigit(char c) { return '0' <= c && c <= '9'; }

vpi ed;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> V;
	F0R(i,V) {
		string x; cin >> x;
		int ind = 0; while (isDigit(x[ind])) ind ++;
		int a = stoi(x.substr(0,ind));
		int b = stoi(x.substr(ind+1,sz(x)-ind-1));
		if (x[ind] == '<') ed.pb({a,b});
		else if (x[ind] == '>') ed.pb({b,a});
		else D.unite(a,b);
	}
	for (auto a: ed) T.addEdge(D.get(a.f),D.get(a.s));
	T.sort();
	T.gen();
	FOR(i,1,M+1) {
		int I = D.get(i);
		int len = T.A[I]+T.B[I]-1;
		if (len == N) cout << "K"<<T.B[I];
		else cout << "?";
		cout << "\n";
	}
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 21732 KB Output is correct
2 Correct 34 ms 21984 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 27196 KB Output is correct
2 Correct 190 ms 28828 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 28828 KB Output is correct
2 Correct 58 ms 28828 KB Output is correct
3 Correct 61 ms 28828 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 41176 KB Output is correct
2 Correct 472 ms 44748 KB Output is correct
3 Correct 459 ms 48504 KB Output is correct
4 Correct 607 ms 59164 KB Output is correct
5 Correct 565 ms 63652 KB Output is correct