EdmondsKarps.cpp

#include <bits/stdc++.h>
using namespace std;

// #define local 0
// #define DEBUG if(local)
// #define VAR(v) #v << "= " << v << " "
// #define COUT cout << "\e[36m" <<
// #define ENDL  "\e[39m" << endl

const int inf = 2000000;
const int unUsed = 0;
const int unUsedAnc = -1;

struct range{
    int x;
    int y;
    int r;
    int id;
    range(int a, int b, int c, int i){
        x = a; y = b; r = c; id = i;
    }
    range(){
        x = y = r = id = 0;
    }
};

template<typename type>
void vectResize(vector<vector<type> > &tab, const int n, const type v){
    tab.clear();
    tab.resize(n, vector<type>(n,v));
}

void read(const int p,const int t, vector<vector<int> > &G);
inline bool inRange(range miner, int x, int y);
void EdmondsKarp(const int p, const int t, vector<vector<int> > &flow, vector<vector<int> > &capacity);


bool solve(vector<vector<int> > &capacity, const int p, const int t){
    vector<vector<int> > flow;
    EdmondsKarp(p,t,flow,capacity);
    for(int i = p; i<=p+t ; i++){
        if(flow[p+t][i]-capacity[p+t][i]){
            return false;
        }
    }
    return true;
}

int main() {
    int z;
    scanf("%d",&z);
    while(z--){
        int p,t;
        scanf("%d%d",&p,&t);
        vector<vector<int> > capacity;
        read(p,t,capacity);
        printf("%s\n",(solve(capacity,p,t) ? "TAK":"NIE"));
    }
}

void read(const int p, const int t, vector<vector<int> > &G) {
    vectResize(G,p+t+1,unUsed);
    vector<range> miner;
    range myself;
    int canGet = 0;
    {
        int x, y, r, d;
        scanf("%d%d%d%d", &x, &y, &r, &d);
        myself = range(x, y, r, 1);
        canGet = d;
    }
    for(int i = 1; i<p ;i++){
        int x, y, r, d;
        scanf("%d%d%d%d",&x,&y,&r,&d);
        miner.push_back(range(x,y,r,i));
        G[0][i] = G[i][0] = d;
    }

    for(int i = p; i<p+t; i++){
        int x, y, f;
        scanf("%d%d%d",&x,&y,&f);

        if(inRange(myself,x,y)) {
            canGet+=f;
            continue;
        }
        for(vector<range>::iterator k = miner.begin(); k!=miner.end(); k++)
            if(inRange(*k,x,y)) {
                G[i][k->id] = inf;
                G[p + t][i] = G[i][p + t] = f;
            }

    }
    for(int i = 1; i<p; i++){
        G[i][0] = G[0][i] = ((canGet - G[0][i])<0 ? 0:canGet-G[0][i]);
    }

}

bool inRange(range miner, int x, int y) {
    return (long long)(miner.x-x)*(long long)(miner.x-x)+(long long)(miner.y-y)*(long long)(miner.y-y)<=(long long)miner.r*(long long)miner.r;
}

bool BFS(const int source, const int outlet, vector<int> &ancestor, vector<int> &residual, vector<vector<int> > &capacity, vector<vector<int> > &flow, const int n){
    ancestor.clear();
    ancestor.resize(n, unUsedAnc);
    ancestor[source] = -2;
    residual[source]=inf;

    queue<int> process;

    while(!process.empty())process.pop();
    process.push(source);
    while (!process.empty()){
        int x = process.front();
        process.pop();
        for (int y = 0; y < n; y++) {
            if(capacity[x][y]-flow[x][y] <=0)
                continue;
            int resCap = capacity[x][y] - flow[x][y];
            if ((resCap == 0) || (ancestor[y] != unUsedAnc))
                continue;
            ancestor[y] = x;
            residual[y] = min(residual[x], resCap);
            if(y==outlet)
                return true;
            process.push(y);
        }
    }
    if(ancestor[outlet]!=unUsedAnc) {
        return true;
    }
    return false;

}

void EdmondsKarp(const int p, const int t, vector<vector<int> > &flow, vector<vector<int> > &capacity) {
    const int n = p+t+1;
    const int source = p+t;
    const int outlet = 0;
    vector<int> ancestor;
    vector<int> residual;

    vectResize(flow,n,0);
    residual.clear();
    residual.resize(n, inf);
    while(BFS(source,outlet,ancestor,residual,capacity,flow,n)){
        int i = outlet;
        while (i != source) {
            int x = ancestor[i];
            flow[x][i] += residual[outlet];
            flow[i][x] -= residual[outlet];
            i = x;
        }
    }
}

findunion.cpp

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct subset{
    int parent;
    int rank;
    subset()
        :rank(0),parent(0)
        {}
    subset(int p, int r)
        :rank(r),parent(p)
        {}
};

int set_find(int x, subset *sets){
    if(sets[x].parent == x)
        return x;
    return sets[x].parent = set_find(sets[x].parent,sets);
}

void set_union(int x, int y, subset *sets){
    x = set_find(x,sets);
    y = set_find(y,sets);
    if(sets[x].rank > sets[y].rank)
        sets[y].parent = x;
    else 
        sets[x].parent = y;
    if(sets[x].rank ==  sets[y].rank)
        sets[y].rank++;
}
inline bool in_board(int x, int y, int n, int m){
    return x>=0 && y>=0 && x<n && y<m;
}

void solve(){
    int n,m;
    cin>>n>>m;
    int **positions = new int*[n*m+1];
    for(int i = 0; i<=n*m; i++)
        positions[i] = new int[2];
    
    int **board = new int*[n];
    for(int i = 0; i<n; i++)
            board[i] = new int[m];
    for(int i = 0; i<n; i++)
        for(int k = 0; k<m; k++){
            int tmp;
            cin>>tmp;
            board[i][k] = tmp;
            positions[tmp][0]=i;
            positions[tmp][1]=k;
        }
    subset *sets = new subset[n*m+1];
    for(int i = 1; i<=n*m; i++){
        sets[i].parent=i;
        sets[i].rank=0;
    }
    int result = 0;
    for(int i = 1; i<=n*m; i++){
        result++;
        for(int mi=-1; mi<=1; mi++)
            for(int mk=-1; mk<=1; mk++)
                if(mi*mk==0 && mi!=mk){
                    int x = positions[i][0]+mi;
                    int y = positions[i][1]+mk;
                    if(in_board(x,y,n,m) && board[x][y]<=i){
                        if(set_find(board[x][y],sets)!=set_find(board[positions[i][0]][positions[i][1]],sets))
                            result--;
                        set_union(board[x][y],board[positions[i][0]][positions[i][1]],sets);
                    }
                }
                    
        cout<<result<<' ';
    }
    cout<<endl;
}

int main() {
    solve();
}

magicz5.cpp

#include<bits/stdc++.h>
using namespace std;
int getInput(int *&tab);

int select(int tab[],int n, int k){
    if(n<=7){
        sort(tab, tab+n);
        return tab[k];
    }

    int *medians = new int[n/5+1];
    for(int i = 0; i<n; i+=5){
        sort(tab+i,tab+i+min(5,n-i));
        medians[i/5] = tab[i+min(2,(n-i)/2)];
    }
    int m = select(medians,n/5+1,(n/5+1)/2);
    delete[] medians;

    int *lesser = new int[n];
    int *equal = new int[n];
    int *greater = new int[n];
    int greaterIndex = 0;
    int lesserIndex = 0;
    int equalIndex = 0;

    for(int i = 0; i<n; i++)
        if(tab[i] < m)
            lesser[lesserIndex++]=tab[i];
        else if(tab[i] == m)
            equal[equalIndex++]=tab[i];
        else
            greater[greaterIndex++]=tab[i];

    if(lesserIndex>k){
        int res = select(lesser,lesserIndex,k);
        delete[] greater;
        delete[] equal;
        delete[] lesser;

        return res;
    }
    else if(lesserIndex+equalIndex>k){
        delete[] lesser;
        delete[] equal;
        delete[] greater;

        return m;
    }
    int res =  select(greater,greaterIndex,k-lesserIndex-equalIndex);

    delete[] lesser;
    delete[] equal;
    delete[] greater;
    return res;
    
}

int main(){
    ios_base::sync_with_stdio(0);
    int *tab=NULL;
    int n = getInput(tab);
    cout<<select(tab,n,n/2)<<endl;
    delete[] tab;
}

int getInput(int *&tab){
    int n;
    cin>>n; 
    tab = new int[n];
    for(int i = 0; i<n; i++)
        cin>>tab[i];
    return n;
}

sat.cpp

#include<bits/stdc++.h>
using namespace std;

int read(vector<vector<int> > &G);
inline int nodeId(int x, bool neg, int n);
void kosaraju(list<int> &processTime,vector<int> &components,vector<vector<int> > G);
vector<vector<int> > reverseEdges(vector<vector<int> > &G);
void dfs(int n,vector<vector<int> > &G, vector<int> &components, int compId);
void dfs(int n, vector<bool> &seen,vector<vector<int> > &G, list<int> &processTime);

bool solveable(int n,vector<int> &components){
    for(int i = 0; i<n; i++){
        if(components[nodeId(i,true,n)]==components[i])
            return false;
    }
    return true;
}
vector<bool> constuctAnswer(int n,list<int> &processTime, vector<int> &components){
    vector<int> values(components.size(),-1);
    
    vector<bool>result(components.size(),false);
    auto it = processTime.begin();
    while(it!=processTime.end()){
        if(result[components[*it]])
            it = processTime.erase(it);
        else{
            result[components[*it]]=true;
            it++;
        }
    }

    while(!processTime.empty()){
        int v = processTime.back();
        processTime.pop_back();
        if(values[components[v]]==-1){
            values[components[v]] = 1;
            values[components[(v<n ? v+n:v-n)]]=0;
        }
    }
    result.clear();
    result.resize(n,false);
    for(int i = 0; i<n; i++)
        result[i]=(values[components[i]]==1);
    return result;
}

void solve(int n, vector<vector<int> > &G){
    vector<int> components;
    list<int> topo;
    kosaraju(topo,components,G);    
    bool res = solveable(n,components);
    cout<<(res ? "TAK":"NIE")<<endl;
    if(!res)
        return;
    vector<bool> ans = constuctAnswer(n,topo,components);
    for(auto i : ans)
        cout<<i<<' ';
    cout<<endl;
}

int main(){
    int z;
    scanf("%d",&z);
    while(z--){
        vector<vector<int> > G;
        int n = read(G);
        solve(n,G);
    }
}

void dfs(int n, vector<bool> &seen,vector<vector<int> > &G, list<int> &processTime){
    if(seen[n])
        return;
    seen[n] = true;
    for(auto i : G[n])
        dfs(i,seen,G,processTime);
    processTime.push_front(n);
}

void dfs(int n,vector<vector<int> > &G, vector<int> &components, int compId){
    if(components[n]!=-1)
        return;
    components[n] = compId;
    for(auto i : G[n])
        dfs(i,G,components,compId);
}

vector<vector<int> > reverseEdges(vector<vector<int> > &G){
    vector<vector<int> > result(G.size());
    for(int i = 0; i<(int)G.size(); i++)
        for(auto k : G[i])
            result[k].push_back(i);
    return result;
}

void kosaraju(list<int> &processTime,vector<int> &components,vector<vector<int> > G){
    const int n = G.size();
    vector<bool> seen(n,false);
    for(int i = 0; i<n; i++)
        dfs(i,seen,G,processTime);
    G = reverseEdges(G);
    for(int i = 0; i<n; i++)
        seen[i] = false;
    components.clear();
    components.resize(n,-1);
    int i = 0;
    for(auto it = processTime.begin(); it!=processTime.end(); it++){
        dfs(*it, G, components,i);
        i++;
    }
}

inline int nodeId(int x, bool neg, int n){
    return (neg ? n:0)+x;
}

 int read(vector<vector<int> > &G){
    int n,m;
    scanf("%d%d",&n,&m);
    G.clear();
    G.resize(2*n);
    for(int i = 0; i<m; i++){
        char sign1, sign2;
        int id1, id2;
        scanf(" %c%d %c%d",&sign1,&id1,&sign2,&id2);
        bool neg1 = (sign1=='-');
        bool neg2 = (sign2=='-');
        id1--;id2--;
        G[nodeId(id1,!neg1,n)].push_back(nodeId(id2,neg2,n));
        G[nodeId(id2,!neg2,n)].push_back(nodeId(id1,neg1,n));
    }
    return n;
}