Submission #1084449

#TimeUsernameProblemLanguageResultExecution timeMemory
1084449AtinaRKOVANICE (COI15_kovanice)C++14
100 / 100
394 ms30588 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...