oj.uz

Submission #1084449

# Submission time Handle Problem Language Result Execution time Memory
1084449 2024-09-06T09:10:07 Z AtinaR KOVANICE (COI15_kovanice) C++14
100 / 100
 394 ms 30588 KB 
#include <bits/stdc++.h>

using namespace std;
int n,m,v;
const int MAX=3*1e5+10;
int parent[MAX];
vector<int> graph[MAX];
int Find(int x)
{
    if(parent[x]==x)return x;
    else return parent[x]=Find(parent[x]);
}
void Unite(int x, int y)
{
    x=Find(x);
    y=Find(y);
    parent[y]=x;
}
int det[MAX];
int dfs(int node)
{
    if(det[node]!=-1)return det[node];
    det[node]=1;
    for(auto x:graph[node])
    {
        det[node]=max(det[node],dfs(x)+1);
    }
    return det[node];
}
int res[MAX];
void dfs2(int node, int step)
{
    if(res[node]!=0)return;
    res[node]=step;
    for(auto x:graph[node])
    {
        if(res[x]==0 && det[node]-1==det[x])
        {
            dfs2(x,step+1);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m>>v;
    for(int i=0; i<m; i++)parent[i]=i;
    vector<pair<int,int> > op;
    bool ind[m];
    memset(res,0,sizeof(res));
    memset(ind,false,sizeof(ind));
    for(int i=0; i<v; i++)
    {
        int a;
        cin>>a;
        char c;
        cin>>c;
        int b;
        cin>>b;
        a--;
        b--;
        if(c=='=')Unite(a,b);
        else op.push_back({a,b});
    }
    for(auto curr:op)
    {
        int a=Find(curr.first),b=Find(curr.second);
        ind[b]=true;
        graph[a].push_back(b);
    }
    memset(det,-1,sizeof(det));
    for(int i=0; i<m; i++)
    {
        if(!ind[i] && graph[i].size()>0 && i==Find(i))
        {
            int tmp=dfs(i);
            if(tmp==n)dfs2(i,1);
        }
    }
    for(int i=0; i<m; i++)
    {
        int tmp=Find(i);
        if(!res[tmp])cout<<"?"<<endl;
        else
            cout<<"K"<<res[tmp]<<endl;
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9820 KB Output is correct
2 Correct 8 ms 9820 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 14156 KB Output is correct
2 Correct 219 ms 14304 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 11732 KB Output is correct
2 Correct 16 ms 11736 KB Output is correct
3 Correct 18 ms 11924 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 22060 KB Output is correct
2 Correct 382 ms 21620 KB Output is correct
3 Correct 394 ms 21448 KB Output is correct
4 Correct 392 ms 23740 KB Output is correct
5 Correct 394 ms 30588 KB Output is correct