제출 #1307679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307679		KhoaDuy	Pictionary (COCI18_pictionary)	C++20	140 / 140	253 ms	4292 KiB

pictionary

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const int MAXN=1e5;
int dsu[MAXN+1];
int Findset(int i){
    if(dsu[i]<0){
        return i;
    }
    int root=Findset(dsu[i]);
    dsu[i]=root;
    return root;
}
void unite(int u,int v){
    u=Findset(u),v=Findset(v);
    if(u==v){
        return;
    }
    if(dsu[u]<dsu[v]){
        swap(u,v);
    }
    dsu[v]+=dsu[u];
    dsu[u]=v;
}
signed main(){
    if(fopen("input.txt","r")){
        freopen("input.txt","r",stdin);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,q;
    cin >> n >> m >> q;
    int a[q],b[q],low[q],high[q];
    for(int i=0;i<q;i++){
        cin >> a[i] >> b[i];
        low[i]=1,high[i]=m;
        low[i]--,high[i]++;
    }
    while(true){
        vector<pair<int,int>> que;
        for(int i=0;i<q;i++){
            if(high[i]-low[i]==1){
                continue;
            }
            int mid=((high[i]-low[i])>>1)+low[i];
            que.push_back({mid,i});
        }
        if(que.empty()){
            break;
        }
        memset(dsu,-1,sizeof(dsu));
        sort(que.begin(),que.end());
        int ptr=-1;
        bool ans[q]={false};
        for(int i=1;i<=m;i++){
            int x=m-i+1;
            for(int y=2*x;y<=n;y+=x){
                unite(x,y);
            }
            while(ptr+1<que.size()&&que[ptr+1].first==i){
                ptr++;
                int idx=que[ptr].second;
                if(Findset(a[idx])==Findset(b[idx])){
                    ans[idx]=true;
                }
            }
        }
        for(int i=0;i<q;i++){
            if(high[i]-low[i]==1){
                continue;
            }
            int mid=((high[i]-low[i])>>1)+low[i];
            if(ans[i]){
                high[i]=mid;
            }
            else{
                low[i]=mid;
            }
        }
    }
    for(int i=0;i<q;i++){
        cout << high[i] << endl;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

pictionary.cpp: In function 'int main()':
pictionary.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14