Submission #1137220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137220		dolphy	KOVANICE (COI15_kovanice)	C++20	10 / 100	62 ms	20912 KiB

kovanice

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb(a) push_back(a)
#define pp pop_back()
#define mp(a, b) make_pair(a, b)
int n, ufds[300005], depth[300005];
bool tried[300005], work[300005];
vector <int> adj[300005];
void init (int n) {
    for (int i=1; i<=n; i++) {ufds[i]=i; depth[i]=-1;}
}
int find (int i) {
    if (ufds[i]==i) return i;
    else return ufds[i]=find(ufds[i]);
}
void mrg (int x, int y) {
    int xrt=find(x);
    int yrt=find(y);
    if (xrt==yrt) return;
    ufds[yrt]=xrt;
}
void dfs (int x) {
    if (tried[x]) return;
    tried[x]=1;
    depth[x]=n;
    for (int i=0; i<adj[x].size(); i++) {
        int c=ufds[adj[x][i]];
        dfs(c);
        depth[x]=min(depth[x], depth[c]-1);
    }
}
void dfs2 (int x) {
    if (tried[x]) return;
    tried[x]=1;
    for (int i=0; i<adj[x].size(); i++) if (depth[adj[x][i]]==depth[x]+1) {
        work[adj[x][i]]=1;
        dfs2(adj[x][i]);
    }
}
int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m, w;
    cin >> n >> m >> w;
    memset(tried, 0, sizeof(tried));
    string eq;
    vector <pair <int, int> > v;
    set <int> s, s2;
    init(m);
    for (int i=0; i<w; i++) {
        cin >> eq;
        int j=0, a=0, b=0, u;
        while ('9'>=eq[j]) {
            a*=10;
            a+=eq[j]-'0';
            j++;
        }
        u=j++;
        while (j<eq.size()) {
            b*=10;
            b+=eq[j]-'0';
            j++;
        }
        if (eq[u]=='=') mrg(a, b);
        else v.pb(mp(a, b));
    }
    for (int i=0; i<v.size(); i++) {
        adj[find(v[i].first)].pb(v[i].second);
    }
    for (int i=1; i<=m; i++) if (!s.count(find(i))) {
        dfs(ufds[i]);
        if (depth[ufds[i]]==1) s2.insert(ufds[i]);
    }
    memset(tried, 0, sizeof(tried));
    memset(work, 0, sizeof(work));
    for (auto it:s2) {
        dfs2(it);
        work[it]=1;
    }
    for (int i=1; i<=m; i++) {
        if (work[ufds[i]]) {
            cout << "K" << depth[ufds[i]] << "\n";
        }
        else cout << "?\n";
    }
    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 10 / 10
• Subtask 4: 0 / 40